14. Minimum Cost to Merge Stones
✅ GFG solution to the Minimum Cost to Merge Stones problem: find minimum cost to merge all stone piles into one using dynamic programming with interval DP technique. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
You are given an array stones[], where the ith element represents the number of stones in the ith pile. In one move, you can merge exactly k consecutive piles into a single pile, and the cost of this move is equal to the total number of stones in these k piles.
Determine the minimum total cost required to merge all the piles into one single pile. If it is not possible to merge all piles into one according to the given rules, return -1.
📘 Examples
Example 1
Input: stones[] = [1, 2, 3], k = 2
Output: 9
Explanation: Initially the array looks like [1, 2, 3].
First, we merge first 2 stones, i.e., 1 and 2, array becomes [3, 3] and cost is 1 + 2 = 3.
Then, we merge remaining stones, i.e., 3 and 3, array becomes [6] and the cost = 3 + 3 = 6.
Total cost = 3 + 6 = 9.Example 2
Input: stones[] = [1, 5, 3, 2, 4], k = 2
Output: 35
Explanation: Initially the array looks like [1, 5, 3, 2, 4].
First, we merge 1 and 5, array becomes [6, 3, 2, 4] and cost is 1 + 5 = 6.
Then, we merge 3 and 2, array becomes [6, 5, 4] and the cost = 3 + 2 = 5.
Then, we merge 5 and 4, array becomes [6, 9] and the cost = 5 + 4 = 9.
Finally, we merge 6 and 9, array becomes [15] and the cost = 6 + 9 = 15.
Total cost = 6 + 5 + 9 + 15 = 35.Example 3
Input: stones[] = [1, 5, 3, 2, 4], k = 4
Output: -1
Explanation: There is no possible way to combine the stones in piles of 4 to get 1 stone in the end.🔒 Constraints
$1 \le \text{stones.size()} \le 30$
$2 \le k \le 30$
$1 \le \text{stones}[i] \le 100$
✅ My Approach
The optimal approach uses Interval Dynamic Programming with Prefix Sum optimization to efficiently compute the minimum cost:
Interval DP + Prefix Sum
Feasibility Check:
For n piles to be merged into 1 pile, we need
(n - 1) % (k - 1) == 0.This is because each merge reduces pile count by
k - 1.If condition fails, return -1 immediately.
Prefix Sum Computation:
Build prefix sum array to calculate range sum in O(1) time.
sum[i]stores total stones from index 0 to i-1.
DP State Definition:
dp[i][j]represents minimum cost to optimally partition range [i, j].Base case:
dp[i][i] = 0(single pile needs no merging).
DP Transition:
For each subrange [i, j], try all valid split points at intervals of
k - 1.Split range into two parts and combine their minimum costs.
If range can be merged into single pile
((j - i) % (k - 1) == 0), add merge cost.
Bottom-Up Computation:
Process subarrays in increasing order of length from k to n.
For each length, iterate through all valid starting positions.
Final answer is stored in
dp[0][n-1].
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(n³), as we iterate over all possible subranges [i, j] and for each range, we try multiple split points. The outer loop runs O(n) times for different lengths, the middle loop runs O(n) times for starting positions, and the inner loop runs O(n/k-1) times for split points, resulting in overall O(n³) complexity.
Expected Auxiliary Space Complexity: O(n²), as we use a 2D DP table of size n×n to store the minimum cost for all possible subranges, and an additional O(n) space for the prefix sum array, resulting in O(n²) auxiliary space.
🧑💻 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> sum(n + 1);
for (int i = 0; i < n; i++) sum[i + 1] = sum[i] + stones[i];
vector<vector<int>> dp(n, vector<int>(n));
for (int len = k; len <= n; len++) {
for (int i = 0; i + len <= n; i++) {
int j = i + len - 1;
dp[i][j] = INT_MAX;
for (int mid = i; mid < j; mid += k - 1)
dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid + 1][j]);
if ((j - i) % (k - 1) == 0)
dp[i][j] += sum[j + 1] - sum[i];
}
}
return dp[0][n - 1];
}
};☕ Code (Java)
class Solution {
public int mergeStones(int[] stones, int k) {
int n = stones.length;
if ((n - 1) % (k - 1) != 0) return -1;
int[] sum = new int[n + 1];
for (int i = 0; i < n; i++) sum[i + 1] = sum[i] + stones[i];
int[][] dp = new int[n][n];
for (int len = k; len <= n; len++) {
for (int i = 0; i + len <= n; i++) {
int j = i + len - 1;
dp[i][j] = Integer.MAX_VALUE;
for (int mid = i; mid < j; mid += k - 1)
dp[i][j] = Math.min(dp[i][j], dp[i][mid] + dp[mid + 1][j]);
if ((j - i) % (k - 1) == 0)
dp[i][j] += sum[j + 1] - sum[i];
}
}
return dp[0][n - 1];
}
}🐍 Code (Python)
class Solution:
def mergeStones(self, stones, k):
n = len(stones)
if (n - 1) % (k - 1): return -1
s = [0] * (n + 1)
for i in range(n): s[i + 1] = s[i] + stones[i]
dp = [[0] * n for _ in range(n)]
for l in range(k, n + 1):
for i in range(n - l + 1):
j = i + l - 1
dp[i][j] = float('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] += s[j + 1] - s[i]
return dp[0][n - 1]🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated