# LeetCode 312: Burst Balloons — Step-by-Step Visual Trace

**Hard** — Dynamic Programming | Array | Interval DP

## The Problem

Given an array of balloons with coin values, find the maximum coins you can collect by bursting all balloons, where bursting a balloon gives coins equal to the product of its value and its adjacent neighbors' values.

## Approach

Uses dynamic programming with interval DP approach. Adds virtual balloons with value 1 at both ends, then for each subarray, tries all possible last balloons to burst and takes the maximum coins achievable.

**Time:** O(n³) · **Space:** O(n²)

## Code

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

        # Add virtual balloons at the beginning and end with a value of 1.
        nums = [1] + nums + [1]

        # Create a 2D table dp to store the maximum coins.
        dp = [[0] * (n + 2) for _ in range(n + 2)]

        # Iterate through different balloon ranges.
        for length in range(2, n + 2):
            for left in range(0, n + 2 - length):
                right = left + length
                for k in range(left + 1, right):
                    # Choose the best order to burst balloons in the range [left, right].
                    dp[left][right] = max(
                        dp[left][right],
                        nums[left] * nums[k] * nums[right] + dp[left][k] + dp[k][right],
                    )

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

## Watch It Run

> **[Open interactive visualization](https://tracelit.dev/app?trace=0312_burst-balloons)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0312_burst-balloons) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*