# LeetCode 312: Burst Balloons

## Problem Restatement

We are given an integer array `nums`.

Each value represents a balloon.

When we burst balloon `i`, we gain coins equal to:

```python
nums[i - 1] * nums[i] * nums[i + 1]
```

If the left or right neighbor is outside the array, treat that missing neighbor as `1`.

After a balloon is burst, it disappears, so its left and right neighbors change.

Return the maximum coins we can collect by choosing the best bursting order.

The official constraints are `1 <= nums.length <= 300` and `0 <= nums[i] <= 100`. The examples include `nums = [3,1,5,8]`, whose answer is `167`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | Maximum coins collectable |
| Action | Burst one balloon at a time |
| Important detail | Neighbors change after each burst |
| Boundary rule | Missing neighbor counts as `1` |

Function shape:

```python
def maxCoins(nums: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [3, 1, 5, 8]
```

One optimal order is:

```text
[3,1,5,8] -> [3,5,8] -> [3,8] -> [8] -> []
```

Coins:

```text
3*1*5 + 3*5*8 + 1*3*8 + 1*8*1
= 15 + 120 + 24 + 8
= 167
```

Output:

```python
167
```

Example 2:

```python
nums = [1, 5]
```

Burst `1` first:

```text
1*1*5 = 5
```

Then burst `5`:

```text
1*5*1 = 5
```

Total:

```python
10
```

Output:

```python
10
```

## First Thought: Try Every Burst Order

A direct solution tries every possible order.

For `n` balloons, there are many orders.

At the first step we can choose any of `n` balloons.

At the next step, any of `n - 1` remaining balloons.

So this becomes roughly:

```python
n!
```

This is far too large for `n <= 300`.

We need dynamic programming.

## Why This Problem Feels Hard

If we think about the first balloon to burst, the subproblems are messy.

Suppose we burst one balloon first. Its two neighbors become adjacent. That changes future coin values.

So choosing the first burst does not cleanly split the array.

The trick is to think in reverse:

Choose the last balloon to burst inside an interval.

When a balloon is the last one left inside an interval, its two outside neighbors are fixed.

That makes the coin calculation stable.

## Add Virtual Boundary Balloons

Add `1` to both ends:

```python
arr = [1] + nums + [1]
```

For example:

```python
nums = [3, 1, 5, 8]
arr = [1, 3, 1, 5, 8, 1]
```

These boundary balloons are never burst.

They only help compute coins at the edges.

## DP Definition

Let:

```python
dp[left][right]
```

mean:

> Maximum coins we can get by bursting all balloons strictly between `left` and `right`.

So `left` and `right` are boundary balloons for the current interval.

They are not burst in this subproblem.

For example:

```python
dp[0][5]
```

means:

> Maximum coins from bursting all original balloons between the two virtual boundaries.

That is the final answer.

## Last Balloon Choice

For interval `(left, right)`, choose some balloon `mid` as the last balloon to burst inside this interval.

Before bursting `mid`, all balloons between `left` and `mid` are gone, and all balloons between `mid` and `right` are gone.

So at that moment, the neighbors of `mid` are exactly:

```python
arr[left]
```

and:

```python
arr[right]
```

Coins from bursting `mid` last:

```python
arr[left] * arr[mid] * arr[right]
```

The left side contributes:

```python
dp[left][mid]
```

The right side contributes:

```python
dp[mid][right]
```

So the transition is:

```python
dp[left][right] = max(
    dp[left][mid] + arr[left] * arr[mid] * arr[right] + dp[mid][right]
)
```

for every `mid` between `left` and `right`.

## Algorithm

1. Build `arr = [1] + nums + [1]`.
2. Create a 2D DP table filled with zeroes.
3. Process intervals by increasing length.
4. For each interval `(left, right)`:
   - Try every `mid` between them.
   - Treat `mid` as the last balloon burst in this interval.
   - Update `dp[left][right]`.
5. Return `dp[0][n + 1]`.

Intervals with no balloon inside have value `0`.

That means when:

```python
right == left + 1
```

there is nothing to burst.

## Correctness

For any interval `(left, right)`, consider an optimal way to burst all balloons inside it.

Among those balloons, one balloon must be burst last. Call it `mid`.

When `mid` is burst last, every other balloon inside `(left, right)` has already disappeared. Therefore, its current neighbors are exactly `left` and `right`.

So the coins from the final burst are:

```python
arr[left] * arr[mid] * arr[right]
```

All balloons between `left` and `mid` must have been burst before that final step. The best possible coins from them are `dp[left][mid]`.

All balloons between `mid` and `right` must also have been burst before that final step. The best possible coins from them are `dp[mid][right]`.

Thus every optimal solution for `(left, right)` has value:

```python
dp[left][mid] + arr[left] * arr[mid] * arr[right] + dp[mid][right]
```

for some valid `mid`.

The algorithm tries every possible `mid`, so it considers the last balloon used by the optimal solution.

Since smaller intervals are computed before larger intervals, both subproblem values are already correct when needed.

Therefore, `dp[left][right]` is correct for every interval, and `dp[0][n + 1]` is the maximum coins for the whole array.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^3)` | There are `O(n^2)` intervals and up to `O(n)` choices of `mid` |
| Space | `O(n^2)` | The DP table stores every interval |

This fits `n <= 300`.

## Implementation

```python
class Solution:
    def maxCoins(self, nums: list[int]) -> int:
        arr = [1] + nums + [1]
        n = len(arr)

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

        for length in range(2, n):
            for left in range(0, n - length):
                right = left + length

                best = 0

                for mid in range(left + 1, right):
                    coins = (
                        dp[left][mid]
                        + arr[left] * arr[mid] * arr[right]
                        + dp[mid][right]
                    )

                    best = max(best, coins)

                dp[left][right] = best

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

## Code Explanation

We add virtual boundary balloons:

```python
arr = [1] + nums + [1]
```

They make every burst have a left and right neighbor.

Create the DP table:

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

`dp[left][right]` stores the best result for the open interval `(left, right)`.

We process by interval length:

```python
for length in range(2, n):
```

Length `2` means there is exactly one balloon between `left` and `right`.

Choose the interval:

```python
for left in range(0, n - length):
    right = left + length
```

Try each possible last balloon:

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

Compute the total if `mid` is burst last:

```python
coins = (
    dp[left][mid]
    + arr[left] * arr[mid] * arr[right]
    + dp[mid][right]
)
```

Keep the best value:

```python
best = max(best, coins)
```

Store it:

```python
dp[left][right] = best
```

The final interval is between the two virtual boundaries:

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

## Testing

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

    assert s.maxCoins([3, 1, 5, 8]) == 167
    assert s.maxCoins([1, 5]) == 10
    assert s.maxCoins([1]) == 1
    assert s.maxCoins([0]) == 0
    assert s.maxCoins([0, 1, 0]) == 1
    assert s.maxCoins([9, 76, 64, 21]) == 116718

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[3, 1, 5, 8]` | Standard example |
| `[1, 5]` | Small array with two choices |
| `[1]` | Single balloon |
| `[0]` | Zero-valued balloon |
| `[0, 1, 0]` | Zeroes around a positive value |
| `[9, 76, 64, 21]` | Larger values and interval interactions |