Burst Balloons
Burst Balloons: choose a balloon-bursting order that maximizes the total coins collected.
- n == nums.length
- 1 <= n <= 300
- 0 <= nums[i] <= 100
Intuition
Burst balloons asks for the bursting order that maximises coins, where bursting balloon i earns nums[left] × nums[i] × nums[right] using its current neighbours. Greedy fails because every burst changes the neighbours of everything around it, so no local rule survives.
The standard DP framing fails too, at first. Trying to decide which balloon to burst first in an interval is hopeless — after that burst the interval splits, but the two halves are no longer independent, since balloons on one side become neighbours of balloons on the other.
The move that unlocks it is to reverse the question:
- Instead of asking which balloon bursts first, ask which balloon bursts last.
That changes everything. If balloon k is the last to burst in the interval (left, right), then at that moment its neighbours are exactly left and right — because everything between them is already gone. So its coins are nums[left] × nums[k] × nums[right], fully determined and independent of the order used earlier.
And now the two sides genuinely are independent: everything left of k bursts entirely within (left, k), everything right within (k, right). Neither can affect the other, because k sits between them until the very end.
Add sentinel balloons of value 1 at both ends so edge balloons use the same formula as interior ones, then try every k as the last burst and take the maximum.
When removing an item changes who becomes adjacent, reverse the decision and ask which item is removed last. If that last choice separates an interval into independent sides, interval DP is the standard pattern.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n^3) time and O(n^2) space.
See why bursting first does not decompose
Removing a balloon first merges its neighbours, so the two remaining sides interact and cannot be solved independently. This is the natural framing and it does not work — recognising that is what motivates the reversal.
Ask which balloon bursts last
If k is last in the interval, its neighbours at that moment are the interval's boundaries, since everything between is already burst. Its coin value is therefore fixed and independent of the earlier order — the property the whole solution rests on.
Add sentinel balloons of value 1
Pad the array with a 1 at each end. Multiplying by 1 is harmless, and it lets balloons at the original edges use the same three-factor formula as interior ones instead of needing special cases.
Define the state as an open interval
solve(left, right) is the maximum coins from bursting everything strictly between those two indices. An empty interval returns 0. Using open boundaries is what keeps the two sentinels intact throughout.
Try every k and combine three parts
For each k in the interval, the total is solve(left, k) + nums[left] * nums[k] * nums[right] + solve(k, right). Take the maximum over all k. The two recursive calls are genuinely independent because k separates them until the end.
Memoise on the interval pair
Cache results keyed by (left, right). There are O(n²) intervals and each tries O(n) choices, so caching is what turns an exponential search into a polynomial one.
Cost of the interval DP
O(n²) states with O(n) work each gives O(n³) time and O(n²) space. That is acceptable for the n ≤ 300 constraint, and the cubic bound is characteristic of interval DP problems like matrix chain multiplication.
Solution & live demo
Common pitfalls
Modeling the first burst
coins = nums[i - 1] * nums[i] * nums[i + 1]
coins = values[left] * values[middle] * values[right]
Original adjacent indices do not remain adjacent after earlier removals; boundaries are known only for the last burst.
Including boundaries in recursive work
solve(left, middle) + solve(middle, right) + solve(middle, middle)
solve(left, middle) + solve(middle, right)
The middle balloon is handled as the last burst and must not appear in either open subinterval.
Omitting sentinel balloons
values = nums
values = [1] + nums + [1]
Sentinels provide the required outside neighbor value for end balloons.
Edge cases
The padded array has no interior index, so the open interval returns zero.
It is last between the two sentinels and earns its own value.
They participate normally; alternative last choices can avoid relying on their zero product.