Minimum Cost to Merge Stones solution and explanation
Google
9 more videos on this problem
Leetcode : Minimum cost to merge stones (Dynamic Programming)Shivank Goel · 32:37 · 23K views
花花酱 LeetCode 1000. Minimum Cost to Merge Stones - 刷题找工作 EP245Hua Hua · 28:15 · 10K views
LeetCode (Hard) - 1000. Minimum Cost to Merge StonesH William Polenz · 36:30 · 8K views
Dynamic Programming Tutorial Using Leetcode Problem 1000 (Minimum Cost to Merge Stones)Emerald Bay · 12:10 · 4K views
1000. Minimum Cost to Merge Stones (Leetcode Hard)Programming Live with Larry · 1:46:52 · 3K views
【每日一题】1000. Minimum Cost to Merge Stones, 04/07/2019Huifeng Guan · 38:57 · 2K views
Minimum Cost to Merge Stones | GFG POTD 14 Nov | LeetCode 100 - Interleaving ProblemAkshay Anil · 21:10 · 2K views
Minimum Cost to Merge Stones | GFG POTD 14 Nov 2025 | Interval DP + Prefix Sum | C++ Solution 🔥Optimal AF · 9:58 · 880 views
猩猩的乐园 Leetcode 1000 Minimum Cost to Merge Stones猩猩的乐园 · 15:59 · 831 views
【点播】Leetcode 1000(hard). Minimum Cost to Merge Stones 【Dynamic Programming】中文AndroidBabies安卓大宝贝们 · 43:54 · 414 views
The 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.
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
Approach overview
Problem Overview: You are given an array of stone piles and an integer k. Each move merges exactly k consecutive piles into one pile, costing the total number of stones in those piles. The goal is to minimize the total merge cost required to combine all piles into a single pile. If it is impossible due to the merge constraint, return -1.
Approach 1: Brute Force Recursive Partitioning (Exponential Time, O(n) space)
The most direct idea tries every valid way to merge k consecutive piles. For each interval, recursively compute the cost of merging left and right partitions, then add the sum of stones when the interval becomes one pile. This approach repeatedly recomputes the same subproblems and explores all possible partitions. Time complexity becomes exponential because each interval branches into multiple merge choices. Space complexity is O(n) for the recursion stack. This method mainly helps you understand the structure of the problem before applying optimization.
Approach 2: Top‑Down Dynamic Programming with Memoization (O(n^3) time, O(n^2) space)
Memoization avoids recomputing subproblems. Define dp(i, j) as the minimum cost to merge piles from index i to j. Only partitions that maintain the ability to merge into valid pile counts are explored. The recursion splits the range at valid positions and stores results in a memo table. To compute the merge cost quickly, use a prefix sum array so the total stones in any interval can be retrieved in O(1). This reduces the brute force explosion but still checks many interval partitions, giving O(n^3) time and O(n^2) space.
Approach 3: Bottom‑Up Dynamic Programming with Prefix Sums (O(n^3) time, O(n^2) space)
The standard optimal solution builds results for increasing interval lengths. Let dp[i][j] represent the minimum cost to merge piles between indices i and j. Iterate over interval lengths and try splitting the segment into two smaller intervals. Because merges only occur in groups of k, partitions advance by k‑1 steps to maintain valid pile counts. A prefix sum array lets you compute the total stones of an interval instantly when a final merge is possible. The algorithm iterates over start index, end index, and partition point, resulting in O(n^3) time and O(n^2) space. This method combines interval dynamic programming with efficient range sum queries on the array.
Recommended for interviews: The bottom‑up DP with prefix sums is the expected solution. Interviewers want to see interval DP reasoning: defining subproblems on ranges, enforcing the k-merge constraint, and using prefix sums to avoid repeated range summations. Starting from the brute force idea and then introducing memoization shows problem‑solving progression, but implementing the optimized DP demonstrates strong algorithmic maturity.
Approach 1: Dynamic Programming with Prefix Sums
Use dynamic programming to minimize the cost. The idea is to store the minimum cost to merge stones from index i to j into p piles. We use prefix sums to calculate the cost of merging stones efficiently.
def mergeStones(stones, k):
n = len(stones)
if (n - 1) % (k - 1): return -1
prefix_sum = [0] * (n + 1)
for i in range(1, n + 1):
prefix_sum[i] = prefix_sum[i - 1] + stones[i - 1]
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] = min(dp[i][m] + dp[m + 1][j] for m in range(i, j, k - 1))
if (j - i) % (k - 1) == 0:
dp[i][j] += prefix_sum[j + 1] - prefix_sum[i]
return dp[0][n - 1]
print(mergeStones([3, 2, 4, 1], 2))class Solution {
public int mergeStones(int[] stones, int k) {
int n = stones.length;
if ((n - 1) % (k - 1) != 0) return -1;
int[] prefixSum = new int[n + 1];
for (int i = 1; i <= n; ++i)
prefixSum[i] = prefixSum[i - 1] + stones[i - 1];
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 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] += prefixSum[j + 1] - prefixSum[i];
}
}
return dp[0][n - 1];
}
}#include <vector>
#include <algorithm>
using namespace std;
int mergeStones(vector<int>& stones, int k) {
int n = stones.size();
if ((n - 1) % (k - 1)) return -1;
vector<int> prefixSum(n + 1, 0);
for (int i = 1; i <= n; ++i)
prefixSum[i] = prefixSum[i - 1] + stones[i - 1];
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int l = k; l <= n; ++l) {
for (int i = 0; i + l <= n; ++i) {
int j = i + l - 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] += prefixSum[j + 1] - prefixSum[i];
}
}
return dp[0][n - 1];
}function mergeStones(stones, k) {
const n = stones.length;
if ((n - 1) % (k - 1) !== 0) return -1;
const prefixSum = Array(n + 1).fill(0);
for (let i = 1; i <= n; ++i) {
prefixSum[i] = prefixSum[i - 1] + stones[i - 1];
}
const dp = Array(n).fill(null).map(() => Array(n).fill(0));
for (let len = k; len <= n; ++len) {
for (let i = 0; i + len <= n; ++i) {
const j = i + len - 1;
dp[i][j] = Infinity;
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] += prefixSum[j + 1] - prefixSum[i];
}
}
}
return dp[0][n - 1];
}
console.log(mergeStones([3, 2, 4, 1], 2));#include <stdio.h>
#include <limits.h>
int mergeStones(int* stones, int stonesSize, int k) {
if ((stonesSize - 1) % (k - 1)) return -1;
int prefixSum[stonesSize + 1];
prefixSum[0] = 0;
for (int i = 1; i <= stonesSize; ++i) {
prefixSum[i] = prefixSum[i - 1] + stones[i - 1];
}
int dp[stonesSize][stonesSize];
for (int length = k; length <= stonesSize; ++length) {
for (int i = 0; i + length <= stonesSize; ++i) {
int j = i + length - 1;
dp[i][j] = INT_MAX;
for (int m = i; m < j; m += (k - 1)) {
dp[i][j] = (dp[i][j] < dp[i][m] + dp[m + 1][j]) ? dp[i][j] : dp[i][m] + dp[m + 1][j];
}
if ((j - i) % (k - 1) == 0) {
dp[i][j] += prefixSum[j + 1] - prefixSum[i];
}
}
}
return dp[0][stonesSize - 1];
}
int main() {
int stones[] = {3, 2, 4, 1};
int k = 2;
printf("%d", mergeStones(stones, 4, k));
return 0;
}public class Solution {
public int MergeStones(int[] stones, int k) {
int n = stones.Length;
if ((n - 1) % (k - 1) != 0) return -1;
int[] prefixSum = new int[n + 1];
for (int i = 1; i <= n; ++i)
prefixSum[i] = prefixSum[i - 1] + stones[i - 1];
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] = int.MaxValue;
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] += prefixSum[j + 1] - prefixSum[i];
}
}
return dp[0, n - 1];
}
}This Python function calculates the minimum cost using a dynamic programming matrix dp[i][j] to store the cost required to merge stones from i to j. We use prefix sums for efficient computation of merge costs.
Time Complexity: O(n^3). Space Complexity: O(n^2).
Approach 2: Default Approach
func mergeStones(stones []int, K int) int {
n := len(stones)
if (n-1)%(K-1) != 0 {
return -1
}
s := make([]int, n+1)
for i, x := range stones {
s[i+1] = s[i] + x
}
f := make([][][]int, n+1)
for i := range f {
f[i] = make([][]int, n+1)
for j := range f[i] {
f[i][j] = make([]int, K+1)
for k := range f[i][j] {
f[i][j][k] = 1 << 20
}
}
}
for i := 1; i <= n; i++ {
f[i][i][1] = 0
}
for l := 2; l <= n; l++ {
for i := 1; i <= n-l+1; i++ {
j := i + l - 1
for k := 2; k <= K; k++ {
for h := i; h < j; h++ {
f[i][j][k] = min(f[i][j][k], f[i][h][k-1]+f[h+1][j][1])
}
}
f[i][j][1] = f[i][j][K] + s[j] - s[i-1]
}
}
return f[1][n][1]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Prefix Sums | Time Complexity: |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recursive Merging | Exponential | O(n) | Conceptual understanding of merge choices; impractical for large inputs |
| Top-Down DP with Memoization | O(n^3) | O(n^2) | Reduces recomputation while keeping recursive structure |
| Bottom-Up DP with Prefix Sums | O(n^3) | O(n^2) | Standard optimal solution for interval DP problems with range sums |
Frequently asked questions
Is Minimum Cost to Merge Stones easy or hard?
Minimum Cost to Merge Stones is classified as a Hard problem. The challenge comes from recognizing it as an interval dynamic programming problem and handling the constraint that exactly k piles must be merged at each step.
Minimum Cost to Merge Stones Python/Java solution
Python and Java implementations typically build a 2D DP table and a prefix sum array. The algorithm iterates over interval lengths, computes optimal partitions, and adds the interval sum when a merge into one pile is valid. Both languages implement the same O(n^3) time and O(n^2) space strategy.
How to solve Minimum Cost to Merge Stones in O(n)?
An O(n) solution is not possible for the general problem because each interval may require evaluating multiple partition points. The known optimal approach is interval dynamic programming with prefix sums, which runs in O(n^3) time.
What is the best approach for Minimum Cost to Merge Stones?
The best approach uses interval Dynamic Programming combined with prefix sums. Define dp[i][j] as the minimum cost to merge piles from index i to j and only consider partitions that maintain valid pile counts based on k. Prefix sums allow constant-time range sum queries when a final merge happens. The overall complexity is O(n^3) time and O(n^2) space.
Is Minimum Cost to Merge Stones asked at Google/Amazon/Meta?
Minimum Cost to Merge Stones represents a classic interval dynamic programming problem often associated with advanced DP interviews. Variations of interval merging and optimal merge cost problems have appeared in interviews at companies like Google, Amazon, and Meta.
What data structure is used in Minimum Cost to Merge Stones?
The solution mainly relies on arrays for the DP table and a prefix sum array for fast range sum queries. The DP table stores the minimum merge cost for every interval of the stones array.
What is the time complexity of Minimum Cost to Merge Stones?
The optimal dynamic programming solution runs in O(n^3) time and uses O(n^2) space. The algorithm iterates over interval lengths, start indices, and partition points while using prefix sums for constant-time range sum queries.