Skip to main content

1000. Minimum Cost to Merge Stones

hard

Merge n piles into one by merging exactly k consecutive piles at a time, paying the sum of stones each merge. Generalized interval DP — the state adds a third dimension for 'how many piles after this interval is merged into'.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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 of stones into one pile. If it is impossible, return -1.

Constraints

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

Examples

Example 1

Input
stones = [3,2,4,1], k = 2
Output
20

Explanation: We start with [3, 2, 4, 1]. We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1]. We merge [4, 1] for a cost of 5, and we are left with [5, 5]. We merge [5, 5] for a cost of 10, and we are left with [10]. The total cost was 20, and this is the minimum possible.

Example 2

Input
stones = [3,2,4,1], k = 3
Output
-1

Explanation: After any merge operation, there are 2 piles left, and we can't merge anymore. So the task is impossible.

Example 3

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

Explanation: We start with [3, 5, 1, 2, 6]. We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6]. We merge [3, 8, 6] for a cost of 17, and we are left with [17]. The total cost was 25, and this is the minimum possible.

Example 4

Input
stones = [6,4,4,6], k = 2
Output
40

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Feasibility check: it's possible iff (n - 1) % (k - 1) == 0. Each merge reduces the pile count by k - 1.

Hint 2

Define dp[i][j][p] = minimum cost to merge stones[i..j] into exactly p piles. Then dp[i][j][1] requires a final k-merge so dp[i][j][1] = dp[i][j][k] + prefix sum of stones[i..j].

Hint 3

For p > 1, split at some t in [i, j) with one side merged into 1 pile, the other into p - 1: dp[i][j][p] = min over t of dp[i][t][1] + dp[t+1][j][p-1].

Hint 4

Prefix sums let you compute interval sums in O(1).

Solution approach

Reveal approach

First, return -1 if (n - 1) % (k - 1) != 0 — every merge shrinks the count by k - 1, so reaching 1 from n is only possible when the gap is a multiple. Build prefix sums. Define dp[i][j][p] as the minimum cost to combine stones[i..j] into p piles. Base case: dp[i][i][1] = 0 (single pile). Recurrence: for p > 1, dp[i][j][p] = min over split t in [i, j) of dp[i][t][1] + dp[t+1][j][p-1]. For p == 1, you must have first reduced to k piles then performed one final merge: dp[i][j][1] = dp[i][j][k] + sum(stones[i..j]). Fill in increasing interval length, then over p. Return dp[0][n-1][1]. A slimmer 2D variant exists when you fix p implicitly using the (length mod (k-1)) constraint.

Complexity

Time
O(n^3 * k)
Space
O(n^2 * k)

Related patterns

  • dynamic-programming
  • interval-dp
  • prefix-sum

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →