LeetCode 1000: Minimum Cost to Merge Stones

Problem Restatement

We are given an array stones.

The ith value tells us how many stones are in pile i.

We are also given an integer k.

In one move, we must merge exactly k consecutive piles into one pile. The cost of that move is the total number of stones in those k piles.

We need to return the minimum total cost to merge all piles into one pile.

If it is impossible, return -1.

The official constraints are n == stones.length, 1 <= n <= 30, 1 <= stones[i] <= 100, and 2 <= k <= 30.

Input and Output

Function shape:

def mergeStones(stones: list[int], k: int) -> int:
    ...

Examples

Example 1:

stones = [3, 2, 4, 1]
k = 2

One optimal sequence:

Total:

5 + 5 + 10 = 20

Answer:

20

Example 2:

stones = [3, 2, 4, 1]
k = 3

A merge reduces 3 piles into 1, so the pile count decreases by 2.

Starting from 4 piles, one merge leaves 2 piles.

But with k = 3, we cannot merge 2 piles.

Answer:

-1

Example 3:

stones = [3, 5, 1, 2, 6]
k = 3

One optimal sequence:

Total:

8 + 17 = 25

Answer:

25

These are the standard examples for the problem.

First Thought: Try Every Merge Order

A direct recursive solution is to try every possible group of k consecutive piles to merge.

After each merge, create the new array and solve the smaller problem.

This follows the problem statement directly, but it is too expensive because the same subproblems appear many times.

Also, the array changes shape after each merge, which makes the recursion awkward.

Key Insight

This is an interval dynamic programming problem.

Because every merge uses consecutive piles, every intermediate pile represents some contiguous interval of the original array.

So instead of thinking about changing arrays, think about ranges:

stones[i:j+1]

We need the minimum cost to reduce each range into a certain number of piles.

A merge of exactly k piles reduces the pile count by:

k - 1

To reduce n piles into 1 pile, the total reduction must be:

n - 1

So merging all piles is possible only if:

(n - 1) % (k - 1) == 0

If this condition fails, return -1.

Algorithm

Use interval DP.

Let:

dp[i][j]

be the minimum cost to merge stones[i:j+1] into as few piles as possible under the merge rule.

For a range length length, after all possible internal merges, the number of piles it can reduce to is determined by:

(length - 1) % (k - 1) + 1

To combine two subranges, split at mid:

stones[i:mid+1]
stones[mid+1:j+1]

Only split positions spaced by k - 1 are useful, because the left side must be reducible to one pile before it can participate cleanly in higher merges.

For each range:

1. Try all valid split points.
2. Minimize:

   dp[i][mid] + dp[mid + 1][j]
3. If the whole range can be merged into one pile, add the sum of the range.

We use prefix sums to compute range sums quickly.

Correctness

Every valid merge sequence over a range can be viewed as first reducing smaller consecutive subranges, then combining their resulting piles.

Therefore, the optimal cost for a range can be built from optimal costs of smaller ranges.

The DP tries every valid split point. For each split, it combines the best cost of the left interval with the best cost of the right interval. Since all merge operations preserve contiguity, every valid merge structure appears in one of these interval splits.

When a range length allows its remaining piles to merge into one pile, the final merge cost is exactly the sum of stones in that range. The DP adds this cost precisely when:

(length - 1) % (k - 1) == 0

This condition means the range can be reduced to one pile.

The base case has cost 0 for a single pile, because no merge is needed.

By processing shorter intervals before longer intervals, every subproblem needed by a larger interval has already been solved. Thus dp[0][n - 1] gives the minimum total cost to merge the full array into one pile.

Complexity

Let n = len(stones).

Since n <= 30, this interval DP is practical.

Implementation

class Solution:
    def mergeStones(self, stones: list[int], k: int) -> int:
        n = len(stones)

        if (n - 1) % (k - 1) != 0:
            return -1

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

        def range_sum(left: int, right: int) -> int:
            return prefix[right + 1] - prefix[left]

        inf = float("inf")
        dp = [[0] * n for _ in range(n)]

        for length in range(k, n + 1):
            for left in range(0, n - length + 1):
                right = left + length - 1
                dp[left][right] = inf

                for mid in range(left, right, k - 1):
                    dp[left][right] = min(
                        dp[left][right],
                        dp[left][mid] + dp[mid + 1][right],
                    )

                if (length - 1) % (k - 1) == 0:
                    dp[left][right] += range_sum(left, right)

        return dp[0][n - 1]

Code Explanation

First check whether merging to one pile is possible:

if (n - 1) % (k - 1) != 0:
    return -1

Each merge reduces the pile count by k - 1, so the total reduction n - 1 must be divisible by k - 1.

Build prefix sums:

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

This lets us get any interval sum in constant time:

return prefix[right + 1] - prefix[left]

The DP table stores minimum costs for intervals:

dp = [[0] * n for _ in range(n)]

Single-pile intervals already cost 0.

We process intervals by increasing length:

for length in range(k, n + 1):

For each interval, try split points:

for mid in range(left, right, k - 1):

The split combines two already-solved intervals:

dp[left][mid] + dp[mid + 1][right]

If this interval can collapse to one pile, add the final merge cost:

if (length - 1) % (k - 1) == 0:
    dp[left][right] += range_sum(left, right)

The final answer is:

return dp[0][n - 1]

Testing

def run_tests():
    s = Solution()

    assert s.mergeStones([3, 2, 4, 1], 2) == 20
    assert s.mergeStones([3, 2, 4, 1], 3) == -1
    assert s.mergeStones([3, 5, 1, 2, 6], 3) == 25
    assert s.mergeStones([1], 2) == 0
    assert s.mergeStones([1, 2, 3], 3) == 6
    assert s.mergeStones([1, 2, 3, 4], 4) == 10

    print("all tests passed")

run_tests()