# Minimum Cost to Merge Stones
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-cost-to-merge-stones)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-to-merge-stones
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## 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.length`
* `1 <= n <= 30`
* `1 <= stones[i] <= 100`
* `2 <= k <= 30`

# Approaches
## Brute-Force Recursion
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.
**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.
**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.
### Explanation
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.
### Algorithm
1. 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`.
2. Define a recursive function, say `solve(current_piles)`, that takes the current arrangement of piles as a list.
3. 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.
4. 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)`.
5. The function should return the minimum cost found among all possible first merges.
6. 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.

## 3D Dynamic Programming
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])`.
**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.
**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)`.
### Explanation
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.

```java
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 i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int p = 0; p <= k; p++) {
                    dp[i][j][p] = 1_000_000_000;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            dp[i][i][1] = 0;
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                for (int p = 2; p <= k; p++) {
                    for (int m = i; m < j; m++) {
                        dp[i][j][p] = Math.min(dp[i][j][p], dp[i][m][p - 1] + dp[m + 1][j][1]);
                    }
                }
                if (dp[i][j][k] != 1_000_000_000) {
                    dp[i][j][1] = dp[i][j][k] + prefix[j + 1] - prefix[i];
                }
            }
        }

        return dp[0][n - 1][1] == 1_000_000_000 ? -1 : dp[0][n - 1][1];
    }
}
```
### Algorithm
1. First, check the condition `(n - 1) % (k - 1) == 0`. If it's not true, return -1.
2. Pre-calculate prefix sums of the `stones` array to quickly compute the sum of any subarray `stones[i...j]` in O(1) time.
3. 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.
4. 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.
5. Iterate through subarray lengths `len` from 2 to `n`.
6. For each `len`, iterate through start indices `i` from 0 to `n-len`. Let `j = i + len - 1`.
7. 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`.
8. 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.
9. The final answer is `dp[0][n-1][1]`.

## Optimized 3D Dynamic Programming
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.
**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.
**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.
### Explanation
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.

```java
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 i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int p = 0; p <= k; p++) {
                    dp[i][j][p] = 1_000_000_000;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            dp[i][i][1] = 0;
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                for (int p = 2; p <= k; p++) {
                    // Optimized loop for split point m
                    for (int m = i; m < j; m += k - 1) {
                        dp[i][j][p] = Math.min(dp[i][j][p], dp[i][m][1] + dp[m + 1][j][p - 1]);
                    }
                }
                if (dp[i][j][k] != 1_000_000_000) {
                    dp[i][j][1] = dp[i][j][k] + prefix[j + 1] - prefix[i];
                }
            }
        }

        return dp[0][n - 1][1] == 1_000_000_000 ? -1 : dp[0][n - 1][1];
    }
}
```
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.
### Algorithm
1. The initial check for `(n - 1) % (k - 1) != 0` and prefix sum calculation remain the same.
2. The DP state `dp[i][j][p]` is also the same: min cost to merge `stones[i...j]` into `p` piles.
3. The base cases are `dp[i][i][1] = 0`.
4. The loops for `len`, `i`, and `p` are structured as in the previous approach.
5. 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])`.
6. 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`.
7. 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.
8. The calculation for `dp[i][j][1]` remains `dp[i][j][k] + sum(stones[i...j])`.
9. The final answer is `dp[0][n-1][1]`.

# Solutions
### Java

```java
class 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 ]; } }
```

### CPP

```cpp
class 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 ]; } };
```

### Python

```python
class 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 ]
```