Minimum Cost to Merge Stones
HardUpdated: Aug 2, 2025
Practice on:
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.
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.
Constraints
n == stones.length1 <= n <= 301 <= stones[i] <= 1002 <= k <= 30
Solution
Method 1 – Dynamic Programming with Prefix Sum
Intuition
We use DP to track the minimum cost to merge subarrays of stones into a certain number of piles. We use prefix sums to quickly calculate the cost of merging. The key is to only merge when the number of piles is reducible to 1 by repeatedly merging k piles.
Approach
- If (n-1) % (k-1) != 0, return -1 (impossible to merge into one pile).
- Compute prefix sums for quick range sum queries.
- Use a 3D DP array: dp[i][j][m] is the min cost to merge stones[i..j] into m piles.
- Base case: dp[i][i][1] = 0.
- For each length, for each i, j, for each m:
- For m > 1, try all possible splits and update dp[i][j][m].
- For m == 1, merge k piles and add the cost.
- The answer is dp[0][n-1][1].
Code
C++
class Solution {
public:
int mergeStones(vector<int>& stones, int k) {
int n = stones.size();
if ((n-1) % (k-1)) return -1;
vector<int> prefix(n+1);
for (int i = 0; i < n; ++i) prefix[i+1] = prefix[i] + stones[i];
vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(k+1, 1e9)));
for (int i = 0; i < n; ++i) dp[i][i][1] = 0;
for (int len = 2; len <= n; ++len) {
for (int i = 0; i+len-1 < n; ++i) {
int j = i+len-1;
for (int m = 2; m <= k; ++m) {
for (int mid = i; mid < j; mid += k-1) {
dp[i][j][m] = min(dp[i][j][m], dp[i][mid][1] + dp[mid+1][j][m-1]);
}
}
if ((len-1) % (k-1) == 0) {
dp[i][j][1] = dp[i][j][k] + prefix[j+1] - prefix[i];
}
}
}
return dp[0][n-1][1];
}
};
Go
func mergeStones(stones []int, k int) int {
n := len(stones)
if (n-1)%(k-1) != 0 {
return -1
}
prefix := make([]int, n+1)
for i := 0; i < n; i++ {
prefix[i+1] = prefix[i] + stones[i]
}
dp := make([][][]int, n)
for i := range dp {
dp[i] = make([][]int, n)
for j := range dp[i] {
dp[i][j] = make([]int, k+1)
for m := range dp[i][j] {
dp[i][j][m] = 1<<30
}
}
}
for i := 0; i < n; i++ {
dp[i][i][1] = 0
}
for l := 2; l <= n; l++ {
for i := 0; i+l-1 < n; i++ {
j := i+l-1
for m := 2; m <= k; m++ {
for mid := i; mid < j; mid += k-1 {
if dp[i][j][m] > dp[i][mid][1]+dp[mid+1][j][m-1] {
dp[i][j][m] = dp[i][mid][1]+dp[mid+1][j][m-1]
}
}
}
if (l-1)%(k-1) == 0 {
dp[i][j][1] = dp[i][j][k] + prefix[j+1] - prefix[i]
}
}
}
return dp[0][n-1][1]
}
Java
class Solution {
public int mergeStones(int[] stones, int k) {
int n = stones.length;
if ((n-1) % (k-1) != 0) return -1;
int[] prefix = new int[n+1];
for (int i = 0; i < n; ++i) prefix[i+1] = prefix[i] + stones[i];
int[][][] dp = new int[n][n][k+1];
for (int[][] arr : dp)
for (int[] a : arr)
Arrays.fill(a, Integer.MAX_VALUE/2);
for (int i = 0; i < n; ++i) dp[i][i][1] = 0;
for (int len = 2; len <= n; ++len) {
for (int i = 0; i+len-1 < n; ++i) {
int j = i+len-1;
for (int m = 2; m <= k; ++m) {
for (int mid = i; mid < j; mid += k-1) {
dp[i][j][m] = Math.min(dp[i][j][m], dp[i][mid][1] + dp[mid+1][j][m-1]);
}
}
if ((len-1) % (k-1) == 0) {
dp[i][j][1] = dp[i][j][k] + prefix[j+1] - prefix[i];
}
}
}
return dp[0][n-1][1];
}
}
Kotlin
class Solution {
fun mergeStones(stones: IntArray, k: Int): Int {
val n = stones.size
if ((n-1) % (k-1) != 0) return -1
val prefix = IntArray(n+1)
for (i in stones.indices) prefix[i+1] = prefix[i] + stones[i]
val dp = Array(n) { Array(n) { IntArray(k+1) { 1_000_000_000 } } }
for (i in 0 until n) dp[i][i][1] = 0
for (len in 2..n) {
for (i in 0..n-len) {
val j = i+len-1
for (m in 2..k) {
for (mid in i until j step k-1) {
dp[i][j][m] = minOf(dp[i][j][m], dp[i][mid][1] + dp[mid+1][j][m-1])
}
}
if ((len-1) % (k-1) == 0) {
dp[i][j][1] = dp[i][j][k] + prefix[j+1] - prefix[i]
}
}
}
return dp[0][n-1][1]
}
}
Python
class Solution:
def mergeStones(self, stones: list[int], k: int) -> int:
n = len(stones)
if (n-1) % (k-1):
return -1
prefix = [0]*(n+1)
for i in range(n):
prefix[i+1] = prefix[i] + stones[i]
dp = [[[float('inf')] * (k+1) for _ in range(n)] for _ in range(n)]
for i in range(n):
dp[i][i][1] = 0
for l in range(2, n+1):
for i in range(n-l+1):
j = i+l-1
for m in range(2, k+1):
for mid in range(i, j, k-1):
dp[i][j][m] = min(dp[i][j][m], dp[i][mid][1] + dp[mid+1][j][m-1])
if (l-1) % (k-1) == 0:
dp[i][j][1] = dp[i][j][k] + prefix[j+1] - prefix[i]
return dp[0][n-1][1]
Rust
impl Solution {
pub fn merge_stones(stones: Vec<i32>, k: i32) -> i32 {
let n = stones.len();
if (n-1) % (k-1) != 0 { return -1; }
let mut prefix = vec![0; n+1];
for i in 0..n { prefix[i+1] = prefix[i] + stones[i]; }
let mut dp = vec![vec![vec![i32::MAX/2; k as usize+1]; n]; n];
for i in 0..n { dp[i][i][1] = 0; }
for len in 2..=n {
for i in 0..=n-len {
let j = i+len-1;
for m in 2..=k as usize {
for mid in (i..j).step_by((k-1) as usize) {
dp[i][j][m] = dp[i][j][m].min(dp[i][mid][1] + dp[mid+1][j][m-1]);
}
}
if (len-1) % (k-1) == 0 {
dp[i][j][1] = dp[i][j][k as usize] + prefix[j+1] - prefix[i];
}
}
}
dp[0][n-1][1]
}
}
TypeScript
class Solution {
mergeStones(stones: number[], k: number): number {
const n = stones.length
if ((n-1) % (k-1) !== 0) return -1
const prefix = Array(n+1).fill(0)
for (let i = 0; i < n; ++i) prefix[i+1] = prefix[i] + stones[i]
const dp = Array.from({length: n}, () => Array.from({length: n}, () => Array(k+1).fill(Infinity)))
for (let i = 0; i < n; ++i) dp[i][i][1] = 0
for (let len = 2; len <= n; ++len) {
for (let i = 0; i+len-1 < n; ++i) {
const j = i+len-1
for (let m = 2; m <= k; ++m) {
for (let mid = i; mid < j; mid += k-1) {
dp[i][j][m] = Math.min(dp[i][j][m], dp[i][mid][1] + dp[mid+1][j][m-1])
}
}
if ((len-1) % (k-1) === 0) {
dp[i][j][1] = dp[i][j][k] + prefix[j+1] - prefix[i]
}
}
}
return dp[0][n-1][1]
}
}
Complexity
- ⏰ Time complexity:
O(n^3/k)— Triple loop for DP, step by k-1. - 🧺 Space complexity:
O(n^2k)— For the DP array.