~25 minutes · Day 71 · Python
Tonight's problem is Burst Balloons, a hard interview-style dynamic programming problem. The trap is that a natural left-to-right simulation keeps changing the neighbors after every burst. Interval DP works because it asks a calmer question: what is the final decision inside a fixed interval?
Decide the LAST balloon to burst in an interval, not the first — with it fixed, the two sides become fully independent subproblems. (Hard — go slow.)
That one sentence is the handle. If you choose the first balloon, the remaining neighbors shift and the subproblems stay tangled. If you choose the last balloon inside an interval, the two border balloons are still sitting there at the end, so the left side and right side can be solved separately.
The brute force is to try every possible burst order. With n balloons there are n! orders, and each order has n bursts, so this is factorial time. It works for tiny inputs and collapses immediately for interview-sized ones.
Dynamic programming means storing answers to subproblems instead of recomputing them (Wikipedia: dynamic programming). For this problem, the subproblem is an open interval: dp[left][right] means “best coins from bursting every balloon strictly between left and right.” The border values are kept by padding the array with two sentinel 1s.
For every interval (left, right), try each inside balloon k as the last one to burst. At that final moment, left and right are its neighbors, so the coins from that final burst are fixed. The two remaining pieces are smaller intervals.
def maxCoins(nums):
vals = [1] + nums + [1] # sentinel borders
n = len(vals)
dp = [[0] * n for _ in range(n)] # dp[left][right]
for width in range(2, n): # shortest intervals first
for left in range(n - width):
right = left + width
dp[left][right] = max(
dp[left][k] + vals[left] * vals[k] * vals[right] + dp[k][right]
for k in range(left + 1, right)
)
return dp[0][n - 1]
The four DP questions are visible here: state is dp[left][right], transition tries the last balloon k, base case is an empty interval worth 0, and the final answer lives at dp[0][n - 1]. Python lists give us the table storage used above (Python docs: data structures).
Classic Matrix Chain Multiplication has the same shape. Given a chain of matrices, where should the final split happen? Predict the move before reading the reveal: is the important decision the first multiplication, or the last split that combines two solved sides?
It is the last split. Choose a split point k, solve the left interval of matrices, solve the right interval, then pay the cost to multiply those two results together. Same interval DP skeleton: every possible k combines two smaller independent intervals.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every order) | O(n! · n) | O(n) |
| Interval DP (last balloon) | O(n³) | O(n²) |
1. What does dp[left][right] mean in this lesson?
left and right. The border balloons stay in place so their values can be used when the final inside balloon bursts.2. Why choose the last balloon inside an interval?
3. Spot the bug in this fill order:
for left in range(n):
for right in range(left + 2, n):
# compute dp[left][right] from smaller intervalsdp[k][right] may not exist yet. Fill by interval width, from short intervals to wide intervals.4. Which clue points to interval DP?
dp[left][right] and choosing the last action.Solve Burst Balloons using the cycle from the training plan: predict → attempt → compare → encode.
Watch NeetCode — Burst Balloons at the compare step. Listen for the moment where the explanation switches from bursting first to choosing the last balloon in an interval.
Stuck or curious? Ask your teacher (the agent) — that's what it's for.