Minimum Cost to Merge Stones

Hard

#0954Time: Exponential, likely in the order of `O(((N-1)/(K-1))!)`. This is because the number of ways to choose merges forms a tree, and the number of states is huge. It will time out for the given constraints.Space: O(N^2) in the recursion stack, as each recursive call reduces the number of piles, and we might have up to N levels of recursion, with each level storing a list of piles.

Patterns

Dynamic Programming Prefix Sum

Data structures

Array

Prompt

There are n piles of stones arranged in a row. The i^th 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.length
1 <= n <= 30
1 <= stones[i] <= 100
2 <= k <= 30

Approaches

3 approaches with complexity analysis and trade-offs.

A brute-force approach involves exploring all possible sequences of merge operations. We can define a recursive function that takes the current state of the piles and tries every possible valid move. A move consists of choosing k consecutive piles and merging them. The cost of this move is added to the cost of subsequent moves, which are found by a recursive call with the updated list of piles. The function returns the minimum cost found across all possible first moves.

Algorithm

First, handle the base case. If (n - 1) % (k - 1) != 0, it's impossible to merge all stones into one pile. This is because each merge operation reduces the number of piles by k - 1. To get from n piles to 1, we need to reduce the pile count by n - 1, which must be a multiple of k - 1.
Define a recursive function, say solve(current_piles), that takes the current arrangement of piles as a list.
The base case for the recursion is when the list contains only one pile (current_piles.size() == 1). In this case, the cost is 0, as no more merges are needed.
In the recursive step, iterate through all possible contiguous sublists of size k. For each such sublist starting at index i: a. Calculate the cost of this merge, which is the sum of stones in these k piles. b. Create a new list of piles by replacing the k piles with a single new pile representing their sum. c. Recursively call solve with this new list of piles: cost + solve(new_piles).
The function should return the minimum cost found among all possible first merges.
To avoid recomputing results for the same pile configuration, a memoization table (a hash map) can be used, where keys are the tuple representation of the pile list and values are the computed minimum costs.

Walkthrough

This method explores the entire search space of merge sequences. Starting with the initial n piles, we look for all possible groups of k consecutive piles to merge. For each choice, we calculate the cost, update the list of piles, and then recursively solve the problem for the new, smaller list of piles. The minimum cost over all initial choices is the answer.

For example, with [s1, s2, s3, s4, s5] and k=3, the first move could be merging [s1, s2, s3] or [s2, s3, s4] or [s3, s4, s5]. The algorithm would explore all three branches and their subsequent sub-branches to find the global minimum cost. Due to the overlapping nature of subproblems (e.g., different merge sequences might lead to the same intermediate pile configuration), this approach is a candidate for memoization, but the state representation is complex, making it difficult to implement efficiently.

Complexity

Time

Exponential, likely in the order of `O(((N-1)/(K-1))!)`. This is because the number of ways to choose merges forms a tree, and the number of states is huge. It will time out for the given constraints.

Space

O(N^2) in the recursion stack, as each recursive call reduces the number of piles, and we might have up to N levels of recursion, with each level storing a list of piles.

Trade-offs

Pros

Conceptually simple and directly follows the problem description.

Cons

Extremely high time complexity, making it infeasible for the given constraints.
The state space is vast because the state is the entire list of piles, not just indices of a subarray.
Memoization is complex to implement because the state (the list of piles) is not simple to hash and store.

A more structured way to solve this problem is using dynamic programming. We can define a state that captures the subproblem of merging a subarray into a specific number of piles. Let dp[i][j][p] be the minimum cost to merge the subarray stones[i...j] into p piles. Our goal is to find dp[0][n-1][1].

The transitions for this DP state can be defined as follows:

To merge stones[i...j] into p piles (where p > 1), we can split the problem at an index m. We merge stones[i...m] into p-1 piles and stones[m+1...j] into 1 pile. The total cost is the sum of costs for these two subproblems. We take the minimum over all possible split points m.
To merge stones[i...j] into 1 pile, we must first merge it into k piles. The cost for this is dp[i][j][k]. Then, we perform the final merge of these k piles, which costs the total sum of stones in stones[i...j]. So, dp[i][j][1] = dp[i][j][k] + sum(stones[i...j]).

Algorithm

First, check the condition (n - 1) % (k - 1) == 0. If it's not true, return -1.
Pre-calculate prefix sums of the stones array to quickly compute the sum of any subarray stones[i...j] in O(1) time.
Create a 3D DP table, dp[n][n][k+1], where dp[i][j][p] stores the minimum cost to merge the subarray stones[i...j] into p piles. Initialize all entries to infinity.
Set the base cases: dp[i][i][1] = 0 for all i from 0 to n-1, as a single pile is already 1 pile with 0 cost.
Iterate through subarray lengths len from 2 to n.
For each len, iterate through start indices i from 0 to n-len. Let j = i + len - 1.
For each (i, j), calculate dp[i][j][p] for p from 2 to k. This is done by splitting the range [i, j] at m: dp[i][j][p] = min(dp[i][j][p], dp[i][m][p-1] + dp[m+1][j][1]) for all m from i to j-1.
After computing costs for p piles, calculate the cost to merge [i, j] into 1 pile: dp[i][j][1] = dp[i][j][k] + sum(stones[i...j]). This is only possible if dp[i][j][k] is not infinity.
The final answer is dp[0][n-1][1].

Walkthrough

The algorithm iterates through all possible subarray lengths and start positions, building up the solution for larger subproblems from smaller ones. A 3D array dp[n][n][k+1] is used for memoization.

Here's a breakdown of the logic:

dp[i][j][1]: The cost to merge stones[i...j] into one pile. This is only possible if we can first form k piles from stones[i...j]. The cost is dp[i][j][k] (cost to get k piles) plus sum(stones[i...j]) (cost of the final merge).
dp[i][j][p] for p > 1: The cost to merge stones[i...j] into p piles. We can achieve this by finding a split point m such that we merge stones[i...m] into p-1 piles and stones[m+1...j] into 1 pile. The total cost is dp[i][m][p-1] + dp[m+1][j][1]. We minimize this over all valid m.

This bottom-up DP approach ensures that when we compute dp[i][j][p], the values for smaller subproblems (dp values for shorter lengths) have already been computed.

1class Solution {2    public int mergeStones(int[] stones, int k) {3        int n = stones.length;4        if ((n - 1) % (k - 1) != 0) {5            return -1;6        }7 8        int[] prefix = new int[n + 1];9        for (int i = 0; i < n; i++) {10            prefix[i + 1] = prefix[i] + stones[i];11        }12 13        int[][][] dp = new int[n][n][k + 1];14        for (int i = 0; i < n; i++) {15            for (int j = 0; j < n; j++) {16                for (int p = 0; p <= k; p++) {17                    dp[i][j][p] = 1_000_000_000;18                }19            }20        }21 22        for (int i = 0; i < n; i++) {23            dp[i][i][1] = 0;24        }25 26        for (int len = 2; len <= n; len++) {27            for (int i = 0; i <= n - len; i++) {28                int j = i + len - 1;29                for (int p = 2; p <= k; p++) {30                    for (int m = i; m < j; m++) {31                        dp[i][j][p] = Math.min(dp[i][j][p], dp[i][m][p - 1] + dp[m + 1][j][1]);32                    }33                }34                if (dp[i][j][k] != 1_000_000_000) {35                    dp[i][j][1] = dp[i][j][k] + prefix[j + 1] - prefix[i];36                }37            }38        }39 40        return dp[0][n - 1][1] == 1_000_000_000 ? -1 : dp[0][n - 1][1];41    }42}

Complexity

Time

O(N^3 * K). The three nested loops for `len`, `i`, and `p` give `O(N*N*K)`, and the inner loop for the split point `m` adds another `O(N)` factor.

Space

O(N^2 * K) for the 3D DP table.

Trade-offs

Pros

Guaranteed to find the optimal solution.
Handles all cases correctly.
Feasible for the given constraints on n and k.

Cons

The time complexity includes a factor of k, which can be up to 30.
The space complexity is relatively high, O(N^2 * K).

This approach builds upon the 3D DP solution by introducing a crucial optimization. The time complexity of the previous approach was dominated by the four nested loops. We can reduce the complexity by being smarter about the transitions.

When calculating dp[i][j][p] = min(dp[i][m][1] + dp[m+1][j][p-1]), we are looking for a split point m. The term dp[i][m][1] represents the cost of merging the subarray stones[i...m] into a single pile. This is only possible if the number of piles in this subarray, m - i + 1, can be reduced to 1. This requires (m - i + 1 - 1) % (k - 1) == 0, which simplifies to (m - i) % (k - 1) == 0.

This observation means we don't need to check every possible split point m. We only need to check m values that satisfy this condition. We can do this by starting m at i and incrementing it by k-1 in each step. This optimization reduces the complexity of the innermost loop from O(N) to O(N/K), leading to an overall improved time complexity.

Algorithm

The initial check for (n - 1) % (k - 1) != 0 and prefix sum calculation remain the same.
The DP state dp[i][j][p] is also the same: min cost to merge stones[i...j] into p piles.
The base cases are dp[i][i][1] = 0.
The loops for len, i, and p are structured as in the previous approach.
The key optimization is in the calculation of dp[i][j][p]. The transition is dp[i][j][p] = min(dp[i][j][p], dp[i][m][1] + dp[m+1][j][p-1]).
We observe that dp[i][m][1] (cost to merge [i,m] into 1 pile) is only meaningful if (m - i) % (k - 1) == 0. This means m-i must be a multiple of k-1.
Therefore, instead of iterating the split point m from i to j-1 (a total of j-i times), we can iterate m from i to j-1 with a step of k-1. This reduces the number of iterations for the inner loop.
The calculation for dp[i][j][1] remains dp[i][j][k] + sum(stones[i...j]).
The final answer is dp[0][n-1][1].

Walkthrough

The implementation is very similar to the standard 3D DP, but with a modified inner loop for the split point m. By changing for (int m = i; m < j; m++) to for (int m = i; m < j; m += k - 1), we significantly reduce the number of computations.

This optimization is valid because any split that doesn't satisfy the condition (m - i) % (k - 1) == 0 would involve an infinite cost for dp[i][m][1], so it would never be chosen as the minimum anyway. By only iterating through the valid split points, we arrive at the same result more efficiently.

1class Solution {2    public int mergeStones(int[] stones, int k) {3        int n = stones.length;4        if ((n - 1) % (k - 1) != 0) {5            return -1;6        }7 8        int[] prefix = new int[n + 1];9        for (int i = 0; i < n; i++) {10            prefix[i + 1] = prefix[i] + stones[i];11        }12 13        int[][][] dp = new int[n][n][k + 1];14        for (int i = 0; i < n; i++) {15            for (int j = 0; j < n; j++) {16                for (int p = 0; p <= k; p++) {17                    dp[i][j][p] = 1_000_000_000;18                }19            }20        }21 22        for (int i = 0; i < n; i++) {23            dp[i][i][1] = 0;24        }25 26        for (int len = 2; len <= n; len++) {27            for (int i = 0; i <= n - len; i++) {28                int j = i + len - 1;29                for (int p = 2; p <= k; p++) {30                    // Optimized loop for split point m31                    for (int m = i; m < j; m += k - 1) {32                        dp[i][j][p] = Math.min(dp[i][j][p], dp[i][m][1] + dp[m + 1][j][p - 1]);33                    }34                }35                if (dp[i][j][k] != 1_000_000_000) {36                    dp[i][j][1] = dp[i][j][k] + prefix[j + 1] - prefix[i];37                }38            }39        }40 41        return dp[0][n - 1][1] == 1_000_000_000 ? -1 : dp[0][n - 1][1];42    }43}

Note: The transition dp[i][j][p] = min(dp[i][m][p-1] + dp[m+1][j][1]) with an optimized loop for m on (j-m-1)%(k-1)==0 also works and yields the same complexity.

Complexity

Time

O(N^3). The loops for `len`, `i`, and `p` are `O(N*N*K)`. The optimized inner loop for `m` runs in `O(N/K)` time. The total complexity is `O(N * N * K * (N/K)) = O(N^3)`.

Space

O(N^2 * K) for the 3D DP table.

Trade-offs

Pros

Most efficient algorithm for the given constraints.
Reduces the number of state transitions checked, improving performance.

Cons

Still requires O(N^2 * K) space, which can be large.
The logic is more subtle than the unoptimized DP.

Solutions

Solution

1class Solution { public int mergeStones ( int [] stones , int K ) { int n = stones . length ; if (( n - 1 ) % ( K - 1 ) != 0 ) { return - 1 ; } int [] s = new int [ n + 1 ]; for ( int i = 1 ; i <= n ; ++ i ) { s [ i ] = s [ i - 1 ] + stones [ i - 1 ]; } int [][][] f = new int [ n + 1 ][ n + 1 ][ K + 1 ]; final int inf = 1 << 20 ; for ( int [][] g : f ) { for ( int [] e : g ) { Arrays . fill ( e , inf ); } } for ( int i = 1 ; i <= n ; ++ i ) { f [ i ][ i ][ 1 ] = 0 ; } for ( int l = 2 ; l <= n ; ++ l ) { for ( int i = 1 ; i + l - 1 <= n ; ++ i ) { int j = i + l - 1 ; for ( int k = 1 ; k <= K ; ++ k ) { for ( int h = i ; h < j ; ++ h ) { f [ i ][ j ][ k ] = Math . min ( f [ i ][ j ][ k ], f [ i ][ h ][ 1 ] + f [ h + 1 ][ j ][ k - 1 ]); } } f [ i ][ j ][ 1 ] = f [ i ][ j ][ K ] + s [ j ] - s [ i - 1 ]; } } return f [ 1 ][ n ][ 1 ]; } }

1class Solution { public: int mergeStones ( vector < int >& stones , int K ) { int n = stones . size (); if (( n - 1 ) % ( K - 1 )) { return - 1 ; } int s [ n + 1 ]; s [ 0 ] = 0 ; for ( int i = 1 ; i <= n ; ++ i ) { s [ i ] = s [ i - 1 ] + stones [ i - 1 ]; } int f [ n + 1 ][ n + 1 ][ K + 1 ]; memset ( f , 0x3f , sizeof ( f )); for ( int i = 1 ; i <= n ; ++ i ) { f [ i ][ i ][ 1 ] = 0 ; } for ( int l = 2 ; l <= n ; ++ l ) { for ( int i = 1 ; i + l - 1 <= n ; ++ i ) { int j = i + l - 1 ; for ( int k = 1 ; k <= K ; ++ k ) { for ( int h = i ; h < j ; ++ h ) { f [ i ][ j ][ k ] = min ( f [ i ][ j ][ k ], f [ i ][ h ][ 1 ] + f [ h + 1 ][ j ][ k - 1 ]); } } f [ i ][ j ][ 1 ] = f [ i ][ j ][ K ] + s [ j ] - s [ i - 1 ]; } } return f [ 1 ][ n ][ 1 ]; } };

1class Solution : def mergeStones ( self , stones : List [ int ], K : int ) -> int : n = len ( stones ) if ( n - 1 ) % ( K - 1 ): return - 1 s = list ( accumulate ( stones , initial = 0 )) f = [[[ inf ] * ( K + 1 ) for _ in range ( n + 1 )] for _ in range ( n + 1 )] for i in range ( 1 , n + 1 ): f [ i ][ i ][ 1 ] = 0 for l in range ( 2 , n + 1 ): for i in range ( 1 , n - l + 2 ): j = i + l - 1 for k in range ( 1 , K + 1 ): for h in range ( i , j ): f [ i ][ j ][ k ] = min ( f [ i ][ j ][ k ], f [ i ][ h ][ 1 ] + f [ h + 1 ][ j ][ k - 1 ]) f [ i ][ j ][ 1 ] = f [ i ][ j ][ K ] + s [ j ] - s [ i - 1 ] return f [ 1 ][ n ][ 1 ]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution { public int mergeStones ( int [] stones , int K ) { int n = stones . length ; if (( n - 1 ) % ( K - 1 ) != 0 ) { return - 1 ; } int [] s = new int [ n + 1 ]; for ( int i = 1 ; i <= n ; ++ i ) { s [ i ] = s [ i - 1 ] + stones [ i - 1 ]; } int [][][] f = new int [ n + 1 ][ n + 1 ][ K + 1 ]; final int inf = 1 << 20 ; for ( int [][] g : f ) { for ( int [] e : g ) { Arrays . fill ( e , inf ); } } for ( int i = 1 ; i <= n ; ++ i ) { f [ i ][ i ][ 1 ] = 0 ; } for ( int l = 2 ; l <= n ; ++ l ) { for ( int i = 1 ; i + l - 1 <= n ; ++ i ) { int j = i + l - 1 ; for ( int k = 1 ; k <= K ; ++ k ) { for ( int h = i ; h < j ; ++ h ) { f [ i ][ j ][ k ] = Math . min ( f [ i ][ j ][ k ], f [ i ][ h ][ 1 ] + f [ h + 1 ][ j ][ k - 1 ]); } } f [ i ][ j ][ 1 ] = f [ i ][ j ][ K ] + s [ j ] - s [ i - 1 ]; } } return f [ 1 ][ n ][ 1 ]; } }

1class Solution { public: int mergeStones ( vector < int >& stones , int K ) { int n = stones . size (); if (( n - 1 ) % ( K - 1 )) { return - 1 ; } int s [ n + 1 ]; s [ 0 ] = 0 ; for ( int i = 1 ; i <= n ; ++ i ) { s [ i ] = s [ i - 1 ] + stones [ i - 1 ]; } int f [ n + 1 ][ n + 1 ][ K + 1 ]; memset ( f , 0x3f , sizeof ( f )); for ( int i = 1 ; i <= n ; ++ i ) { f [ i ][ i ][ 1 ] = 0 ; } for ( int l = 2 ; l <= n ; ++ l ) { for ( int i = 1 ; i + l - 1 <= n ; ++ i ) { int j = i + l - 1 ; for ( int k = 1 ; k <= K ; ++ k ) { for ( int h = i ; h < j ; ++ h ) { f [ i ][ j ][ k ] = min ( f [ i ][ j ][ k ], f [ i ][ h ][ 1 ] + f [ h + 1 ][ j ][ k - 1 ]); } } f [ i ][ j ][ 1 ] = f [ i ][ j ][ K ] + s [ j ] - s [ i - 1 ]; } } return f [ 1 ][ n ][ 1 ]; } };

1class Solution : def mergeStones ( self , stones : List [ int ], K : int ) -> int : n = len ( stones ) if ( n - 1 ) % ( K - 1 ): return - 1 s = list ( accumulate ( stones , initial = 0 )) f = [[[ inf ] * ( K + 1 ) for _ in range ( n + 1 )] for _ in range ( n + 1 )] for i in range ( 1 , n + 1 ): f [ i ][ i ][ 1 ] = 0 for l in range ( 2 , n + 1 ): for i in range ( 1 , n - l + 2 ): j = i + l - 1 for k in range ( 1 , K + 1 ): for h in range ( i , j ): f [ i ][ j ][ k ] = min ( f [ i ][ j ][ k ], f [ i ][ h ][ 1 ] + f [ h + 1 ][ j ][ k - 1 ]) f [ i ][ j ][ 1 ] = f [ i ][ j ][ K ] + s [ j ] - s [ i - 1 ] return f [ 1 ][ n ][ 1 ]

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.