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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Minimum Cost to Merge Stones and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →