Minimum Cost to Merge Stones — Problem & Solution
Minimum Cost to Merge Stones solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Minimum Cost to Merge Stones is a hard coding problem on arrays, dynamic programming and prefix sum, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Prefix Sum
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n piles of stones in a row, and pile i holds stones[i] stones.
A move merges exactly k consecutive piles into a single pile, and it costs the total number of stones in those k piles. The new pile takes their place in the row.
Return the minimum total cost to merge all the piles into one pile, or -1 if that is impossible.
Example 1
Input: stones = [6,2,5,1], k = 2
Output: 28
Explanation: Merge `[6,2]` (cost 8) and `[5,1]` (cost 6), then `[8,6]` (cost 14): 28 in total.
Example 2
Input: stones = [6,2,5,1], k = 3
Output: -1
Explanation: Each move removes exactly 2 piles, so 4 piles can only become 2, never 1.
Example 3
Input: stones = [2,6,1,3,5], k = 3
Output: 26
Explanation: Merge `[2,6,1]` (cost 9) to get `[9,3,5]`, then merge everything (cost 17).
Constraints
n == stones.length1 <= n <= 301 <= stones[i] <= 1002 <= k <= 30
Hints for Minimum Cost to Merge Stones
Hint 1
Each move reduces the number of piles by
k - 1. When cannpiles end as one?Hint 2
Let
dp[i][j]be the cheapest way to mergestones[i..j]into as few piles as possible. The leftmost of those piles comes from some prefixstones[i..mid]that was merged all the way down to one pile.Hint 3
Only prefixes with
mid - ia multiple ofk - 1can become a single pile, so stepmidbyk - 1:dp[i][j] = min(dp[i][mid] + dp[mid+1][j]). When(j - i)is itself a multiple ofk - 1, the range can finish as one pile — add its stone total.
How to solve Minimum Cost to Merge Stones
Every move turns k piles into one, removing k - 1, so n piles become one exactly when (n - 1) % (k - 1) == 0. More generally a range of length L can be reduced to (L - 1) % (k - 1) + 1 piles and no fewer. An interval DP over ranges, splitting off the leftmost final pile, captures every merge order.
Approach
- If
(n - 1) % (k - 1) != 0, return-1. - Build prefix sums so any range total is O(1).
dp[i][i] = 0. For lengths 2 tonand every starti(endj):dp[i][j] = min over mid = i, i + (k-1), i + 2(k-1), … < j of dp[i][mid] + dp[mid+1][j].- If
(j - i) % (k - 1) == 0, the range's piles can be merged one final time into one pile: addsum(i..j)todp[i][j]. - Return
dp[0][n - 1].
Why it works
Look at the minimal pile configuration of stones[i..j]: its leftmost pile came from some prefix stones[i..mid] merged into one pile, which is only possible when mid - i is a multiple of k - 1 — hence the step. The rest of the range is handled independently, because merges never cross the boundary between the leftmost pile's stones and the others before that final step. When the whole range reduces to exactly k piles, one more merge costs precisely the range total, whatever order came before — so adding sum(i..j) at those lengths accounts for the last merge.
Complexity
- Time —
O(n^3 / (k - 1)) - Space —
O(n^2)
Pitfalls
- Check feasibility first — without it the DP happily returns a cost for a row that can never become one pile.
- Step the split point by
k - 1, not by 1; other split points describe prefixes that cannot be a single pile. - Add the range sum only when
(len - 1) % (k - 1) == 0; adding it elsewhere charges merges that never happen.
Reference solution
Python
from typing import List
def mergeStones(stones: List[int], k: int) -> int:
n = len(stones)
if (n - 1) % (k - 1) != 0:
return -1
pre = [0] * (n + 1)
for i in range(n):
pre[i + 1] = pre[i] + stones[i]
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
best = 10 ** 18
for mid in range(i, j, k - 1):
cand = dp[i][mid] + dp[mid + 1][j]
if cand < best:
best = cand
if (length - 1) % (k - 1) == 0:
best += pre[j + 1] - pre[i]
dp[i][j] = best
return dp[0][n - 1]Java
public static int mergeStones(int[] stones, int k) {
int n = stones.length;
if ((n - 1) % (k - 1) != 0) return -1;
int[] pre = new int[n + 1];
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + stones[i];
int[][] dp = new int[n][n];
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len <= n; i++) {
int j = i + len - 1;
int best = Integer.MAX_VALUE;
for (int mid = i; mid < j; mid += k - 1) best = Math.min(best, dp[i][mid] + dp[mid + 1][j]);
if ((len - 1) % (k - 1) == 0) best += pre[j + 1] - pre[i];
dp[i][j] = best;
}
}
return dp[0][n - 1];
}C++
int mergeStones(vector<int>& stones, int k) {
int n = stones.size();
if ((n - 1) % (k - 1) != 0) return -1;
vector<int> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + stones[i];
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len <= n; i++) {
int j = i + len - 1;
int best = INT_MAX;
for (int mid = i; mid < j; mid += k - 1) best = min(best, dp[i][mid] + dp[mid + 1][j]);
if ((len - 1) % (k - 1) == 0) best += pre[j + 1] - pre[i];
dp[i][j] = best;
}
}
return dp[0][n - 1];
}JavaScript
var mergeStones = function(stones, k) {
var n = stones.length;
if ((n - 1) % (k - 1) !== 0) return -1;
var pre = new Array(n + 1).fill(0);
for (var i = 0; i < n; i++) pre[i + 1] = pre[i] + stones[i];
var dp = [];
for (var i = 0; i < n; i++) dp.push(new Array(n).fill(0));
for (var len = 2; len <= n; len++) {
for (var i = 0; i + len <= n; i++) {
var j = i + len - 1, best = Infinity;
for (var mid = i; mid < j; mid += k - 1) {
best = Math.min(best, dp[i][mid] + dp[mid + 1][j]);
}
if ((len - 1) % (k - 1) === 0) best += pre[j + 1] - pre[i];
dp[i][j] = best;
}
}
return dp[0][n - 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming