Dynamic Programming · LC #312
Burst Balloons
Interval DP where `k` is the LAST balloon burst in range `[l, r]`, not the first. Padding with virtual 1s handles boundary multiplications. Build bottom-up by increasing interval length.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given `n` balloons with values `nums`, bursting balloon `i` earns `nums[i-1] * nums[i] * nums[i+1]` coins (out-of-bound values treated as 1). Return the maximum coins collectible by bursting all balloons.
Sample I/O
Input: nums = [3,1,5,8] Output: 167 (burst order: 1→15, 5→120, 3→24, 8→8; total=167) Input: nums = [1,5] Output: 10
Intuition
How to Think About It
Intuition
Thinking of the first balloon to burst leads to complex overlapping subproblems (neighbours change after each burst). The key inversion: think of `k` as the LAST balloon to burst in `[l, r]`. When `k` is last, its left and right neighbours are the fixed virtual borders `b[l-1]` and `b[r+1]` - they haven't been burst yet.
Core Concept
Pad `nums` with 1s at both ends: `b = [1, ...nums, 1]`. `dp[l][r]` = max coins from bursting all balloons in `(l, r)` exclusive. Transition: for each k in [l, r], `dp[l][r] = max(dp[l][r], b[l]*b[k]*b[r] + dp[l][k] + dp[k][r])`. Build by increasing interval length.
When to use
Problems where merging or removing elements changes the neighbourhood of remaining elements - interval DP with "last operation" inversion is the go-to pattern.
When NOT to use
When the order of operations doesn't affect neighbours (simpler DP suffices). When intervals don't overlap in their dependencies (use divide & conquer without memoisation).
Key Insights
What to Know Cold
- The "last burst" inversion is the non-obvious insight that makes the recurrence clean; "first burst" leads to unsolvable subproblem dependencies.
- Padding with 1s eliminates boundary conditions - no special-casing for i=0 or i=n-1.
- dp[l][r] is defined over the open interval (l, r) exclusive - balloons l and r are virtual borders, not burst within this subproblem.
- Filling order: increase interval length from 1 to n; for each length iterate all valid l positions.
- Memoised top-down recursion is equivalent and may be easier to code in an interview setting.
1 example
Worked Examples
Burst [3,1,5,8] for maximum coins
Optimal: burst 1 first (3×1×5=15), then 5 (3×5×8=120), then 3 (1×3×8=24), then 8 (1×8×1=8) → 167.
Interval DP: pad with 1s, treat k as last burst, fill by increasing interval length.
Output: 167
One of the hardest standard DP problems; the "last operation" inversion trick is a transferable insight for Stone Merge, Zuma Game, and other interval-destruction problems tested at Google.