Burst Balloons: The Interval DP That Rewards Thinking Backwards
The interval DP solution to Burst Balloons, explained by choosing the last balloon to burst — intuition, JavaScript code, a walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Burst Balloons is where dynamic programming stops feeling like memorized templates and starts demanding real insight. The prompt sounds like a greedy problem — pop balloons, collect coins, get the biggest total — but every greedy heuristic you try falls apart, because the reward for popping a balloon depends on which of its neighbors are still standing.
The trick that cracks it is almost paradoxical: instead of asking which balloon do I burst first, you ask which balloon do I burst last inside every sub-range. That one reframe turns a tangled, order-dependent mess into clean, independent subproblems — the hallmark of interval DP.
The problem
You're given an array nums of n balloons, each painted with a number. When you burst balloon i, you collect nums[i - 1] * nums[i] * nums[i + 1] coins. If a neighbor is off the edge of the array (or already burst), treat it as a 1. Burst all the balloons and return the maximum coins possible.
Input: nums = [3, 1, 5, 8]
Output: 167
One optimal order:
burst 1 → 3*1*5 = 15 remaining [3, 5, 8]
burst 5 → 3*5*8 = 120 remaining [3, 8]
burst 3 → 1*3*8 = 24 remaining [8]
burst 8 → 1*8*1 = 8 remaining []
total = 15 + 120 + 24 + 8 = 167The catch is right there in the coin formula: nums[i - 1] and nums[i + 1] change as balloons disappear. Bursting a balloon early gives its neighbors different partners than bursting it late. Order is everything, and there are n! orders.
The brute force baseline
The literal reading is: try every possible sequence of bursts. Pick a balloon, collect its coins, remove it, recurse on what's left.
function maxCoinsBrute(nums) {
if (nums.length === 0) return 0;
let best = 0;
for (let i = 0; i < nums.length; i++) {
const left = i > 0 ? nums[i - 1] : 1;
const right = i < nums.length - 1 ? nums[i + 1] : 1;
const coins = left * nums[i] * right;
const rest = [...nums.slice(0, i), ...nums.slice(i + 1)];
best = Math.max(best, coins + maxCoinsBrute(rest));
}
return best;
}This is correct but explores every permutation of bursts — O(n!) time. Ten balloons already means 3.6 million orderings, and 15 balloons is over a trillion. Worse, the recursion can't be memoized cleanly: after a few bursts the "remaining" array can be any subset of balloons, so there's no compact state to cache.
The key insight: burst it last, not first
Why is memoizing the brute force so hard? Because when you burst balloon i first, you split the array into a left part and a right part — but those two parts aren't independent. A balloon on the far left can still burst against a balloon on the far right later, once everything between them is gone. The subproblems bleed into each other.
Flip it. Suppose inside some interval, balloon i is the last one you burst. By the time it pops, every other balloon in that interval is already gone, so its two neighbors are exactly the balloons at the interval's boundaries — and those never move. That cleanly cuts the interval into two independent halves: everything to the left of i, and everything to the right of i. Neither half can ever reach across i, because i is still standing until the very end.
To make the boundaries always exist, pad the array with virtual 1 balloons on both ends: balloons = [1, ...nums, 1]. Now a real edge balloon always has a real neighbor to multiply against — the padding contributes a harmless 1.
Define dp[L][R] as the max coins from bursting every balloon strictly between indices L and R (the bounds themselves are never burst in this subproblem). If balloon i is the last to burst in (L, R), it earns balloons[L] * balloons[i] * balloons[R], plus the best from the left sub-interval dp[L][i] and the right sub-interval dp[i][R]:
dp[L][R] = max over i in (L, R) of
dp[L][i] + dp[i][R] + balloons[L] * balloons[i] * balloons[R]The optimal solution
Because a bigger interval depends on smaller ones, fill the table by increasing window length len. Shorter windows resolve first, so every dp[L][i] and dp[i][R] is already computed when you need it.
function maxCoins(nums) {
// Pad with virtual balloons of value 1 so every burst has two valid neighbors
const balloons = [1, ...nums, 1];
const n = balloons.length;
// dp[L][R] = max coins from bursting all balloons strictly between L and R
const dp = Array.from({ length: n }, () => new Array(n).fill(0));
// len is the window size (distance between the L and R bounds)
for (let len = 2; len < n; len++) {
for (let L = 0; L < n - len; L++) {
let R = L + len;
// i is the LAST balloon to burst inside interval (L, R)
for (let i = L + 1; i < R; i++) {
const coinsBurstingI = balloons[L] * balloons[i] * balloons[R];
const total = dp[L][i] + dp[i][R] + coinsBurstingI;
dp[L][R] = Math.max(dp[L][R], total);
}
}
}
return dp[0][n - 1];
}Windows of length under 2 hold no burstable balloon, so dp starts at 0 and those cells stay 0 — that's the base case, free. The answer lives at dp[0][n - 1]: the max coins across the entire padded interval, which is exactly the whole original array.
Walkthrough
Trace nums = [1, 5, 8]. After padding, balloons = [1, 1, 5, 8, 1] with n = 5. The table fills by window length, and each row below is one candidate i the loop tries; the running dp[L][R] keeps the max.
| len | (L, R) | i | coins = b[L]·b[i]·b[R] | dp[L][i] + dp[i][R] | total | dp[L][R] |
|---|---|---|---|---|---|---|
| 2 | (0, 2) | 1 | 1·1·5 = 5 | 0 + 0 | 5 | 5 |
| 2 | (1, 3) | 2 | 1·5·8 = 40 | 0 + 0 | 40 | 40 |
| 2 | (2, 4) | 3 | 5·8·1 = 40 | 0 + 0 | 40 | 40 |
| 3 | (0, 3) | 1 | 1·1·8 = 8 | 0 + 40 | 48 | 48 |
| 3 | (0, 3) | 2 | 1·5·8 = 40 | 5 + 0 | 45 | 48 |
| 3 | (1, 4) | 2 | 1·5·1 = 5 | 0 + 40 | 45 | 45 |
| 3 | (1, 4) | 3 | 1·8·1 = 8 | 40 + 0 | 48 | 48 |
| 4 | (0, 4) | 1 | 1·1·1 = 1 | 0 + 48 | 49 | 49 |
| 4 | (0, 4) | 2 | 1·5·1 = 5 | 5 + 40 | 50 | 50 |
| 4 | (0, 4) | 3 | 1·8·1 = 8 | 48 + 0 | 56 | 56 |
The final dp[0][4] = 56. Read the winning row: inside the full interval (0, 4), bursting balloon 8 (index 3) last wins — it earns 1·8·1 = 8 against the two padding boundaries, and the left sub-interval dp[0][3] = 48 already banked the coins from popping 1 and 5 first. That decomposition is exactly what "burst last" buys you.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force (all orders) | O(n!) | O(n) | every permutation of bursts, no cacheable state |
| Interval DP | O(n³) | O(n²) | O(n²) intervals, each scanning O(n) choices of last balloon |
There are roughly n²/2 intervals (L, R), and for each the inner loop tries every balloon between them — up to n candidates. That's three nested loops over the padded array: O(n³). The table itself is an n × n grid, giving O(n²) space.
Common mistakes
- Trying to pick the first balloon to burst. It feels natural, but bursting first leaves the two halves entangled — a left balloon can still touch a right balloon later. Only "burst last" makes the sub-intervals independent.
- Forgetting the sentinel padding. Without
[1, ...nums, 1], edge balloons index out of bounds and you special-case every boundary. The1s multiply harmlessly and make the recurrence uniform. - Treating
LandRas burst inside the subproblem.dp[L][R]counts only balloons strictly between the bounds; the bounds are the surviving neighbors, not part of the interval's coins. - Iterating in the wrong order. If you don't grow
lenfrom small to large (or memoize top-down), you'll readdp[L][i]before it's computed and get garbage. Shorter windows must finish first. - Using coins from a shrinking
numsin the recurrence. The coins for last-burstialways use the fixed boundary valuesballoons[L]andballoons[R], never the live neighbors from a simulated pop order.
Where this pattern shows up next
Burst Balloons is the boss level of one-dimensional DP. Before tackling interval DP, most people build intuition on the linear-recurrence problems where each state depends on a couple of earlier ones:
- Fibonacci Number — the simplest DP recurrence, and the mental model for "state built from earlier states."
- Climbing Stairs — the same recurrence dressed as counting paths.
- Min Cost Climbing Stairs — a tiny optimization twist on the stairs recurrence.
- House Robber — the first "max value with a choice at each index" DP, one dimension below intervals.
You can also step through Burst Balloons interactively to watch the dp[L][R] table fill window by window and see the last-burst boundaries light up.
FAQ
Why does Burst Balloons pick the last balloon to burst instead of the first?
Choosing the first balloon to burst splits the array into a left and right part that are not independent — a balloon on the left can still burst against one on the right once the balloons between them are gone. Choosing the last balloon to burst inside an interval is the opposite: by the time it pops, everything else in that interval is already gone, so its neighbors are exactly the fixed interval boundaries. That makes the left and right sub-intervals truly independent, which is what lets you cache and combine them as a DP.
Why do we pad the array with 1s?
Padding nums into [1, ...nums, 1] guarantees every balloon always has two valid neighbors to multiply against, including the original edge balloons. The virtual 1s never get burst — they only serve as boundary multipliers — and multiplying by 1 adds nothing, so they don't distort any coin count. Without them, you'd have to special-case bursts at index 0 and index n - 1 in the recurrence, which is exactly the kind of edge handling the sentinels remove.
What is the time and space complexity of the DP solution?
Time is O(n³) and space is O(n²). There are about n²/2 intervals (L, R) to fill, and for each interval the inner loop tries every balloon between the bounds as the last one to burst — up to n candidates — so three nested loops give O(n³). The dp table is an n × n grid of interval answers, which is O(n²) space. This crushes the O(n!) brute force that tries every burst ordering.
Can Burst Balloons be solved with top-down memoization instead?
Yes. You can write a recursive solve(L, R) that returns the best coins for the open interval (L, R), trying each i between L and R as the last burst and memoizing on the (L, R) pair. It computes the exact same values as the bottom-up table and has the same O(n³) time and O(n²) space. The bottom-up version shown here just makes the fill order explicit — grow the window length so every smaller sub-interval is ready before you need it.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.