You are given an array of integers stones of length n and an integer K. The goal is to merge the stones into one pile. Each time, you can merge exactly K consecutive piles into one, and the cost of this merge is the total number of stones in those K piles. The new pile's size is the sum of those K piles. You repeat this process until only one pile remains. Return the minimum possible total cost to merge all stones into one pile. If it is impossible, return -1.
K consecutive piles at a time.K piles being merged.-1.
Key constraints:
- 1 <= stones.length <= 30
- 2 <= K <= 30
- All elements in stones are positive integers.
Let's break down the problem:
K consecutive piles at a time.K-1.n and K.n grows. Instead, we need to find a way to break the problem into smaller subproblems and use dynamic programming to avoid redundant calculations.
The main insight is to use DP to store the minimum cost to merge a subarray of stones into a certain number of piles. We also need to be careful with the merge rules, ensuring we only merge when it's allowed by K.
We use a dynamic programming approach to solve this problem efficiently:
(n - 1) % (K - 1) == 0. Otherwise, return -1 immediately.dp[i][j][m] be the minimum cost to merge the subarray stones[i:j+1] into m piles.dp[0][n-1][1], the minimum cost to merge the entire array into one pile.dp[i][i][1] = 0 for all i, since a single pile needs no merges.stones[i:j+1] into m piles, try all possible split points and number of left piles:mid from i to j-1, and leftPiles from 1 to m-1:
dp[i][j][m] = min(dp[i][j][m], dp[i][mid][leftPiles] + dp[mid+1][j][m-leftPiles])m == 1 and dp[i][j][K] is available (i.e., we can merge K piles into 1), then add the cost of merging: dp[i][j][1] = dp[i][j][K] + sum(stones[i:j+1])dp[0][n-1][1] is possible, return it; otherwise, return -1.This approach efficiently computes the minimum cost by breaking the problem into overlapping subproblems and avoiding redundant calculations.
Example:
stones = [3, 2, 4, 1], K = 2
n = 4, K = 2(n-1) % (K-1) = (4-1) % (2-1) = 3 % 1 = 0, so merging to one pile is possible.Brute-force approach:
n.O(K^{n}) (not feasible for large n).O(n^2) subarrays, and for each, up to K piles.O(n) split points.O(n^3 K).O(n^2 K) for the DP table.
This is efficient enough for the problem's constraints (n <= 30).
The "Minimum Cost to Merge Stones" problem is a classic example of interval dynamic programming, where the challenge is to merge subarrays optimally under strict rules. The key insight is to model the problem as merging subarrays into a given number of piles and use a 3D DP table to store intermediate results. By carefully managing transitions and using prefix sums for efficient cost calculation, we avoid redundant work and solve the problem efficiently. This approach highlights the power of dynamic programming for problems with overlapping subproblems and complex merge rules.
from functools import lru_cache
from math import inf
class Solution:
def mergeStones(self, stones, K):
n = len(stones)
if (n - 1) % (K - 1) != 0:
return -1
prefix = [0] * (n + 1)
for i in range(n):
prefix[i+1] = prefix[i] + stones[i]
@lru_cache(None)
def dp(i, j, m):
if i == j:
return 0 if m == 1 else inf
if m == 1:
cost = dp(i, j, K)
if cost == inf:
return inf
return cost + prefix[j+1] - prefix[i]
res = inf
for mid in range(i, j, K-1):
left = dp(i, mid, 1)
right = dp(mid+1, j, m-1)
if left != inf and right != inf:
res = min(res, left + right)
return res
ans = dp(0, n-1, 1)
return ans if ans != inf else -1
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
public:
int mergeStones(vector<int>& stones, int K) {
int n = stones.size();
if ((n - 1) % (K - 1) != 0) return -1;
vector<int> prefix(n + 1, 0);
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, INT_MAX)));
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) {
if (dp[i][mid][1] == INT_MAX || dp[mid+1][j][m-1] == INT_MAX) continue;
dp[i][j][m] = min(dp[i][j][m], dp[i][mid][1] + dp[mid+1][j][m-1]);
}
}
if (dp[i][j][K] != INT_MAX) {
dp[i][j][1] = dp[i][j][K] + prefix[j+1] - prefix[i];
}
}
}
return dp[0][n-1][1] == INT_MAX ? -1 : dp[0][n-1][1];
}
};
import java.util.Arrays;
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[][] arr2d : dp)
for (int[] arr1d : arr2d)
Arrays.fill(arr1d, Integer.MAX_VALUE);
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) {
if (dp[i][mid][1] == Integer.MAX_VALUE || dp[mid+1][j][m-1] == Integer.MAX_VALUE) continue;
dp[i][j][m] = Math.min(dp[i][j][m], dp[i][mid][1] + dp[mid+1][j][m-1]);
}
}
if (dp[i][j][K] != Integer.MAX_VALUE) {
dp[i][j][1] = dp[i][j][K] + prefix[j+1] - prefix[i];
}
}
}
return dp[0][n-1][1] == Integer.MAX_VALUE ? -1 : dp[0][n-1][1];
}
}
var mergeStones = function(stones, K) {
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) {
let j = i + len - 1;
for (let m = 2; m <= K; ++m) {
for (let mid = i; mid < j; mid += K-1) {
if (dp[i][mid][1] === Infinity || dp[mid+1][j][m-1] === Infinity) continue;
dp[i][j][m] = Math.min(dp[i][j][m], dp[i][mid][1] + dp[mid+1][j][m-1]);
}
}
if (dp[i][j][K] !== Infinity) {
dp[i][j][1] = dp[i][j][K] + prefix[j+1] - prefix[i];
}
}
}
return dp[0][n-1][1] === Infinity ? -1 : dp[0][n-1][1];
};