How do you approach Minimum Cost to Merge Stones?

First check if merging is possible: (n - 1) must be divisible by (k - 1).

What is the time complexity of Minimum Cost to Merge Stones?

Time complexity: O(n^3 / k). Space complexity: O(n^2).

What are common mistakes on Minimum Cost to Merge Stones?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

gitGood.dev

← Back to problems

Minimum Cost to Merge Stones

HardAlgorithms

Description

There are n piles of stones arranged in a row. The ith pile has stones[i] stones.

A move consists of merging exactly k consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these k piles.

Return the minimum cost to merge all piles into one pile. If it is impossible, return -1.

Example 1

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

Output: 20

Explanation: Merge [3,2] cost 5, then [4,1] cost 5, then [5,5] cost 10. Total = 20.

Example 2

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

Output: -1

Explanation: We cannot merge all piles with k=3 since (4-1) is not divisible by (3-1).

Example 3

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

Output: 25

Constraints

- 1 <= stones.length <= 30 - 1 <= stones[i] <= 100 - 2 <= k <= 30

Minimum Cost to Merge Stones: approach, complexity and pitfalls

A hard dynamic programming problem, graded against 6 test cases (3 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

If you are stuck

Show the 3-step hint ladder

First check if merging is possible: (n - 1) must be divisible by (k - 1).
Use interval DP: dp[i][j] = minimum cost to optimally process stones from i to j.
Split intervals at steps of (k - 1) and add the merge cost when the interval can be reduced to one pile.

The optimal approach

Show the approach: Interval DP

First check feasibility: (n-1) % (k-1) must equal 0. Use prefix sums for range sum queries. Define dp[i][j] as the minimum cost to process stones[i..j]. Split at multiples of (k-1) from i. When (j-i) % (k-1) == 0, the range can be merged into one pile, so add the range sum.

Time: O(n^3 / k)
Space: O(n^2)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.