Minimum Cost to Merge Stones
Problem
There are n piles of stones in a row; the i-th pile has stones[i] stones. A move merges exactly K consecutive piles into one new pile, costing the total number of stones in those K piles. Return the minimum total cost to merge all piles into one pile, or -1 if it is impossible.
stones = [3, 2, 4, 1], K = 220def merge_stones(stones, K):
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]
INF = float("inf")
dp = [[0] * n for _ in range(n)]
for length in range(K, n + 1):
for i in range(0, n - length + 1):
j = i + length - 1
dp[i][j] = INF
for m in range(i, j, K - 1):
dp[i][j] = min(dp[i][j], dp[i][m] + dp[m + 1][j])
if (j - i) % (K - 1) == 0:
dp[i][j] += pre[j + 1] - pre[i]
return dp[0][n - 1]function mergeStones(stones, K) {
const n = stones.length;
if ((n - 1) % (K - 1) !== 0) return -1;
const pre = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) pre[i + 1] = pre[i] + stones[i];
const INF = Infinity;
const dp = Array.from({ length: n }, () => new Array(n).fill(0));
for (let len = K; len <= n; len++) {
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
dp[i][j] = INF;
for (let m = i; m < j; m += K - 1)
dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m + 1][j]);
if ((j - i) % (K - 1) === 0) dp[i][j] += pre[j + 1] - pre[i];
}
}
return dp[0][n - 1];
}class Solution {
public 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 = K; len <= n; len++)
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = Integer.MAX_VALUE;
for (int m = i; m < j; m += K - 1)
dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m + 1][j]);
if ((j - i) % (K - 1) == 0) dp[i][j] += pre[j + 1] - pre[i];
}
return dp[0][n - 1];
}
}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 = K; len <= n; len++)
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = INT_MAX;
for (int m = i; m < j; m += K - 1)
dp[i][j] = min(dp[i][j], dp[i][m] + dp[m + 1][j]);
if ((j - i) % (K - 1) == 0) dp[i][j] += pre[j + 1] - pre[i];
}
return dp[0][n - 1];
}Explanation
Each move merges exactly K consecutive piles into one, paying the total stones in them. We want to reduce everything to a single pile as cheaply as possible. This is interval DP over ranges of piles, sped up with prefix sums.
First a feasibility check: each merge removes K-1 piles, so reaching one pile is only possible when (n-1) % (K-1) == 0; otherwise we return -1. Prefix sums let us read the total of any range as pre[j+1] - pre[i] instantly.
dp[i][j] is the minimum cost to merge the range i..j into as few piles as possible. For each range we try split points m stepping by K-1, combining dp[i][m] + dp[m+1][j]. If the range can collapse fully to one pile ((j-i) % (K-1) == 0), we add its range sum once for that final merge.
Example: stones = [3,2,4,1], K=2. Merging [3,2] (5), then [4,1] (5), then the two 5s (10) totals 20, found at dp[0][n-1].
There are O(n²) ranges and each scans up to O(n/K) splits, giving roughly O(n³ / K) time with O(n²) space.