Minimum Cost to Merge Stones: Interval DP

You have n piles of stones in a row. The i-th pile has stones[i] stones. In one move, you pick exactly k consecutive piles and merge them into a single pile. The cost of that move equals the total number of stones in those k piles. Find the minimum total cost to merge everything into one pile. If it is impossible, return -1.

This is 1000. Minimum Cost to Merge Stones, and it is one of the hardest interval DP problems on LeetCode. When k = 2 it reduces to the classic stone merging problem, but for general k the recurrence has a subtle twist that trips up most people on the first attempt.

When is merging even possible?

Each merge operation reduces the number of piles by exactly k - 1. Starting from n piles and ending at 1 pile means you need to remove n - 1 piles total. Since each move removes k - 1, you need (n - 1) to be divisible by (k - 1). If (n - 1) % (k - 1) != 0, return -1 immediately.

This is a quick sanity check before you touch any DP logic.

Prefix sums for range costs

Every time you merge k piles into one, the cost is the sum of all stones in those piles. You will compute many range sums throughout the DP, so precompute a prefix sum array:

prefix[0] = 0
prefix[i] = stones[0] + stones[1] + ... + stones[i-1]

The sum of stones[i..j] is then prefix[j + 1] - prefix[i], which is O(1) per query.

The interval DP recurrence

Define dp[i][j] as the minimum cost to merge piles i through j into as few piles as possible. "As few as possible" means: if (j - i) % (k - 1) == 0, the interval collapses into exactly one pile. Otherwise it reduces to some number of piles greater than one, and the cost so far does not include a final merge for that interval.

The recurrence has two parts:

Splitting. For each split point m from i to j - 1, stepping by k - 1:

dp[i][j] = min(dp[i][m] + dp[m + 1][j])

You step m by k - 1 because the left half [i..m] must itself be reducible to one pile, which requires (m - i) % (k - 1) == 0.

Merging. After finding the best split, check whether the full interval [i..j] can collapse to one pile. If (j - i) % (k - 1) == 0, add the cost of that final merge:

dp[i][j] += prefix[j + 1] - prefix[i]

This is the part that catches people. You only add the range sum when the interval length allows a full collapse to one pile. If it does not, dp[i][j] just stores the cost of the intermediate merges, and some outer interval will eventually pay the final merge cost.

Python solution

def mergeStones(stones: list[int], k: int) -> int:
    n = len(stones)
    if (n - 1) % (k - 1) != 0:
        return -1

    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + stones[i]

    dp = [[0] * n for _ in range(n)]
    for length in range(k, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float("inf")
            for m in range(i, j, k - 1):
                dp[i][j] = min(dp[i][j], dp[i][m] + dp[m + 1][j])
            if (j - i) % (k - 1) == 0:
                dp[i][j] += prefix[j + 1] - prefix[i]

    return dp[0][n - 1]

The outer loop goes from interval length k (the smallest mergeable group) up to n. For each interval [i, j], you try all valid split points stepping by k - 1. After picking the cheapest split, you tack on the range sum if this interval fully collapses.

Step-by-step walkthrough

Complexity analysis

Time: O(n^3 / k). There are O(n^2) intervals. For each interval, the inner loop steps by k - 1, so it runs O(n / k) times per interval. Total work is O(n^2 * n / k) = O(n^3 / k).

Space: O(n^2). The DP table has one entry per interval, and the prefix sum array uses O(n) additional space.

For n up to 30 (the constraint for this problem), even the loosest bound of O(n^3) is well under a million operations.

The building blocks

Interval DP with conditional merge cost. The core pattern here is the same one behind Burst Balloons and Matrix Chain Multiplication: define a DP over intervals, enumerate split points, and fill the table by increasing length. The twist for Minimum Cost to Merge Stones is that you only add the merge cost when the interval length permits a full collapse to one pile. This "conditional cost" idea generalizes to any problem where you merge groups of a fixed size rather than pairs. Recognizing that the merge cost applies conditionally, not unconditionally, is what separates this problem from the standard stone merge.

Prefix sums for O(1) range queries. Precomputing cumulative sums so that any subarray sum is available in constant time is one of the most reusable techniques in competitive programming. Here it turns what would be an O(n) summation per interval into an O(1) lookup. You will see prefix sums in problems ranging from subarray sum queries to 2D matrix sums to sliding window calculations. Building it is a single pass, and it eliminates an entire factor of n from your runtime.

Edge cases to watch for

• Impossible merges: n = 4, k = 3. (4 - 1) % (3 - 1) = 1, which is not zero. Return -1.
• Single pile: n = 1. No merges needed, return 0.
• Already exactly k piles: n = k. One merge of everything, cost = sum of all stones.
• k = 2: Reduces to the classic stone merge problem. Every pair of consecutive piles can merge, and every interval of length >= 2 collapses to one pile.

From understanding to recall

Reading through this solution once gives you the shape of the idea, but it will not stick without practice. The tricky parts are remembering to step the split point by k - 1, remembering when to add the range sum, and not confusing this recurrence with the simpler k = 2 version.

Spaced repetition locks these details in. You solve this problem from scratch, wait a day, solve it again, wait three days, solve it again. Each rep forces you to reconstruct the conditional merge cost logic and the (n - 1) % (k - 1) feasibility check. After a few reps, those details become automatic rather than something you have to re-derive.

The interval DP pattern and the prefix sum technique are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding problems at random and hoping the patterns stick.

Related posts

• Burst Balloons - The classic interval DP problem where you think about the last action in each interval, a close cousin to the merge-cost recurrence
• Stone Game - Another stone-pile problem, this time solved with game theory DP over intervals
• Minimum Cost for Tickets - A different flavor of cost-minimization DP where you pick the cheapest option at each step