# LeetCode 1000: Minimum Cost to Merge Stones

## Problem Restatement

We are given an array `stones`.

The `i`th value tells us how many stones are in pile `i`.

We are also given an integer `k`.

In one move, we must merge exactly `k` consecutive piles into one pile. The cost of that move is the total number of stones in those `k` piles.

We need to return the minimum total cost to merge all piles into one pile.

If it is impossible, return `-1`.

The official constraints are `n == stones.length`, `1 <= n <= 30`, `1 <= stones[i] <= 100`, and `2 <= k <= 30`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `stones` and integer `k` |
| Output | Minimum total merge cost |
| Move | Merge exactly `k` consecutive piles |
| Cost | Sum of stones in the merged piles |
| Impossible case | Return `-1` |

Function shape:

```python
def mergeStones(stones: list[int], k: int) -> int:
    ...
```

## Examples

Example 1:

```python
stones = [3, 2, 4, 1]
k = 2
```

One optimal sequence:

| Move | New piles | Cost |
|---|---|---:|
| Merge `[3, 2]` | `[5, 4, 1]` | `5` |
| Merge `[4, 1]` | `[5, 5]` | `5` |
| Merge `[5, 5]` | `[10]` | `10` |

Total:

```python
5 + 5 + 10 = 20
```

Answer:

```python
20
```

Example 2:

```python
stones = [3, 2, 4, 1]
k = 3
```

A merge reduces `3` piles into `1`, so the pile count decreases by `2`.

Starting from `4` piles, one merge leaves `2` piles.

But with `k = 3`, we cannot merge `2` piles.

Answer:

```python
-1
```

Example 3:

```python
stones = [3, 5, 1, 2, 6]
k = 3
```

One optimal sequence:

| Move | New piles | Cost |
|---|---|---:|
| Merge `[5, 1, 2]` | `[3, 8, 6]` | `8` |
| Merge `[3, 8, 6]` | `[17]` | `17` |

Total:

```python
8 + 17 = 25
```

Answer:

```python
25
```

These are the standard examples for the problem.

## First Thought: Try Every Merge Order

A direct recursive solution is to try every possible group of `k` consecutive piles to merge.

After each merge, create the new array and solve the smaller problem.

This follows the problem statement directly, but it is too expensive because the same subproblems appear many times.

Also, the array changes shape after each merge, which makes the recursion awkward.

## Key Insight

This is an interval dynamic programming problem.

Because every merge uses consecutive piles, every intermediate pile represents some contiguous interval of the original array.

So instead of thinking about changing arrays, think about ranges:

```python
stones[i:j+1]
```

We need the minimum cost to reduce each range into a certain number of piles.

A merge of exactly `k` piles reduces the pile count by:

```python
k - 1
```

To reduce `n` piles into `1` pile, the total reduction must be:

```python
n - 1
```

So merging all piles is possible only if:

```python
(n - 1) % (k - 1) == 0
```

If this condition fails, return `-1`.

## Algorithm

Use interval DP.

Let:

```python
dp[i][j]
```

be the minimum cost to merge `stones[i:j+1]` into as few piles as possible under the merge rule.

For a range length `length`, after all possible internal merges, the number of piles it can reduce to is determined by:

```python
(length - 1) % (k - 1) + 1
```

To combine two subranges, split at `mid`:

```python
stones[i:mid+1]
stones[mid+1:j+1]
```

Only split positions spaced by `k - 1` are useful, because the left side must be reducible to one pile before it can participate cleanly in higher merges.

For each range:

1. Try all valid split points.
2. Minimize:
   ```python id="g89bda"
   dp[i][mid] + dp[mid + 1][j]
   ```
3. If the whole range can be merged into one pile, add the sum of the range.

We use prefix sums to compute range sums quickly.

## Correctness

Every valid merge sequence over a range can be viewed as first reducing smaller consecutive subranges, then combining their resulting piles.

Therefore, the optimal cost for a range can be built from optimal costs of smaller ranges.

The DP tries every valid split point. For each split, it combines the best cost of the left interval with the best cost of the right interval. Since all merge operations preserve contiguity, every valid merge structure appears in one of these interval splits.

When a range length allows its remaining piles to merge into one pile, the final merge cost is exactly the sum of stones in that range. The DP adds this cost precisely when:

```python
(length - 1) % (k - 1) == 0
```

This condition means the range can be reduced to one pile.

The base case has cost `0` for a single pile, because no merge is needed.

By processing shorter intervals before longer intervals, every subproblem needed by a larger interval has already been solved. Thus `dp[0][n - 1]` gives the minimum total cost to merge the full array into one pile.

## Complexity

Let `n = len(stones)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^3 / k)` | For each interval, we try split points stepping by `k - 1` |
| Space | `O(n^2)` | DP table stores costs for intervals |

Since `n <= 30`, this interval DP is practical.

## Implementation

```python
class Solution:
    def mergeStones(self, stones: list[int], k: int) -> int:
        n = len(stones)

        if (n - 1) % (k - 1) != 0:
            return -1

        prefix = [0] * (n + 1)
        for i, value in enumerate(stones):
            prefix[i + 1] = prefix[i] + value

        def range_sum(left: int, right: int) -> int:
            return prefix[right + 1] - prefix[left]

        inf = float("inf")
        dp = [[0] * n for _ in range(n)]

        for length in range(k, n + 1):
            for left in range(0, n - length + 1):
                right = left + length - 1
                dp[left][right] = inf

                for mid in range(left, right, k - 1):
                    dp[left][right] = min(
                        dp[left][right],
                        dp[left][mid] + dp[mid + 1][right],
                    )

                if (length - 1) % (k - 1) == 0:
                    dp[left][right] += range_sum(left, right)

        return dp[0][n - 1]
```

## Code Explanation

First check whether merging to one pile is possible:

```python
if (n - 1) % (k - 1) != 0:
    return -1
```

Each merge reduces the pile count by `k - 1`, so the total reduction `n - 1` must be divisible by `k - 1`.

Build prefix sums:

```python
prefix = [0] * (n + 1)
for i, value in enumerate(stones):
    prefix[i + 1] = prefix[i] + value
```

This lets us get any interval sum in constant time:

```python
return prefix[right + 1] - prefix[left]
```

The DP table stores minimum costs for intervals:

```python
dp = [[0] * n for _ in range(n)]
```

Single-pile intervals already cost `0`.

We process intervals by increasing length:

```python
for length in range(k, n + 1):
```

For each interval, try split points:

```python
for mid in range(left, right, k - 1):
```

The split combines two already-solved intervals:

```python
dp[left][mid] + dp[mid + 1][right]
```

If this interval can collapse to one pile, add the final merge cost:

```python
if (length - 1) % (k - 1) == 0:
    dp[left][right] += range_sum(left, right)
```

The final answer is:

```python
return dp[0][n - 1]
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.mergeStones([3, 2, 4, 1], 2) == 20
    assert s.mergeStones([3, 2, 4, 1], 3) == -1
    assert s.mergeStones([3, 5, 1, 2, 6], 3) == 25
    assert s.mergeStones([1], 2) == 0
    assert s.mergeStones([1, 2, 3], 3) == 6
    assert s.mergeStones([1, 2, 3, 4], 4) == 10

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `[3,2,4,1]`, `2` | `20` | Standard binary merge case |
| `[3,2,4,1]`, `3` | `-1` | Impossible pile count reduction |
| `[3,5,1,2,6]`, `3` | `25` | Standard ternary merge case |
| `[1]`, `2` | `0` | Already one pile |
| `[1,2,3]`, `3` | `6` | One direct merge |
| `[1,2,3,4]`, `4` | `10` | One direct merge |