Algorithm

Burst Balloons

Dynamic Programming Pattern

Burst Balloons

You are given an array nums where nums[i] is the number painted on the i-th balloon. You burst all the balloons one at a time, in any order you choose. Bursting balloon i earns nums[left] × nums[i] × nums[right] coins, where left and right are the balloons immediately adjacent to i among those still unburst; if a side has no remaining balloon, treat it as a 1. After a balloon bursts, its neighbours become adjacent to each other. Return the maximum coins you can collect.

CONSTRAINTS
  • 1 ≤ nums.length ≤ 300
  • 0 ≤ nums[i] ≤ 100
  • Out-of-range neighbours count as 1, not 0
  • Every balloon must eventually be burst
EXAMPLE 1
Input: nums = [3, 1, 5, 8]
Output: 167
Bursting in the order 1, 5, 3, 8 earns 15, then 120, then 24, then 8. Popping the largest balloon early would forfeit the large products it contributes to as a neighbour.
EXAMPLE 2
Input: nums = [1, 5]
Output: 10
Bursting the 1 first earns 1 × 1 × 5 = 5 and then 1 × 5 × 1 = 5. Bursting the 5 first earns only 5 and then 1, for a total of 6.
EXAMPLE 3
Input: nums = [7]
Output: 7
A single balloon has no real neighbours, so both sides count as 1 and the payoff is 1 × 7 × 1.
EXAMPLE 4
Input: nums = [2, 3]
Output: 9
Bursting the 2 first earns 1 × 2 × 3 = 6 and leaves the 3 to earn 1 × 3 × 1 = 3, for 9. Bursting the 3 first earns 6 and then only 2, for 8.
EXAMPLE 5
Input: nums = [0, 5, 0]
Output: 5
Both zeros pay nothing whenever they burst, so pop them first and the 5 is left alone with padding on each side, earning 1 × 5 × 1. A zero neighbour would have wiped out the 5's payoff, which is why clearing them first is worth doing.
What counts as a neighbour after some balloons have burst?
The nearest balloon still standing on each side. When one bursts, its neighbours become adjacent to each other, which is why the payoff for a given balloon depends entirely on the order chosen.
What happens at the ends of the array?
A missing neighbour counts as 1, not 0. This matters enormously — treating it as 0 would zero out every payoff at the boundary. Padding the array with 1s at both ends is the cleanest way to encode the rule.
Do I have to burst every balloon?
Yes, all of them, in some order of your choosing. Since values are non-negative, there is never an incentive to stop early anyway, but the contract does require it.
Can a balloon's value be zero?
Yes. A zero balloon earns nothing when burst and zeroes out any product it participates in as a neighbour, so it effectively splits the array into independent regions — the table handles that without special treatment.
Would it help to burst the largest balloon first?
No, and the intuition usually runs the wrong way here. A large value is worth more standing than burst, because it multiplies the payoff of every neighbour that bursts beside it. That inversion is a good sign that no greedy ordering will work.
Why the obvious framing traps you

Bursting a balloon pays you the product of it and its two current neighbours, and then the array closes up. So the array is constantly changing shape, and which balloons are adjacent depends on everything you have already burst.

The natural first thought is to pick a balloon to burst first and recurse on what remains. Try to write down that state and you immediately hit a wall. After the first burst, the remaining balloons are the original array minus one element — that is not a contiguous stretch of the original, it is an arbitrary subset. To describe it you would need a set of surviving indices, and there are 2ⁿ of those. The table would have more entries than atoms in the room.

Worse, the subproblems are not independent. Bursting a balloon in the left half changes who the neighbours are in the middle, so the two halves cannot be solved separately.

Key Insightwhen choosing what happens first creates a mess, ask what happens last. This is the same move that solved Matrix Chain Multiplication, and it works here for the same underlying reason — fixing the last event leaves independent pieces, while fixing the first does not.
Fixing the last balloon in a range

Consider a stretch of balloons from index i to index j, and suppose we are going to burst all of them while everything outside that stretch is still intact. One of them is burst last; call it k.

Now the payoff. At the moment k bursts, every other balloon in i..j is already gone, so its two neighbours are whatever sits immediately outside the range: nums[i-1] and nums[j+1]. Those are known, fixed values that do not depend on the order used inside the range. So bursting k last earns exactly

nums[i-1] × nums[k] × nums[j+1]

And before that, the balloons in i..k-1 were all burst — with k still standing as their right-hand wall — and the balloons in k+1..j were all burst, with k still standing as their left-hand wall. Those two groups never interact, because k sits between them the entire time and never disappears until the end. Each is an independent subproblem of exactly the same kind.

That is the whole solution, and it is worth checking why the "first" framing failed by comparison: if you burst k first, the two sides become adjacent immediately and their fates are entangled. Bursting it last keeps them separated by a wall. The last-burst view is what buys independence.

State Definitionf(i, j) is the maximum coins obtainable by bursting every balloon strictly inside the open range (i, j), assuming balloons i and j are still standing.

Using open boundaries makes the arithmetic cleaner than inclusive ones. With that definition:

f(i, j) = max over k strictly between i and j of [ f(i, k) + f(k, j) + nums[i] × nums[k] × nums[j] ]

Base case: if j == i + 1 there is nothing between them, so f = 0.

The padding trick

The statement says a missing neighbour counts as 1. Rather than writing boundary checks everywhere, add a 1 at each end of the array. Multiplying by 1 changes nothing, so the padded array behaves identically while every real balloon now has genuine neighbours on both sides.

python
def max_coins(nums):
    balloons = [1] + nums + [1]
    n = len(balloons)
    memo = {}

    def f(i, j):
        if j <= i + 1: return 0                   # nothing strictly between
        if (i, j) in memo: return memo[(i, j)]
        best = 0
        for k in range(i + 1, j):                 # k is burst LAST in this range
            coins = (f(i, k) + f(k, j)
                     + balloons[i] * balloons[k] * balloons[j])
            best = max(best, coins)
        memo[(i, j)] = best
        return best

    return f(0, n - 1)

The answer is f(0, n-1) — burst everything strictly between the two padded ones, which is exactly the original array.

Cost: about N² intervals, each trying up to N split points, giving O(N³) time and O(N²) space. For 300 balloons that is around 27 million operations, which runs comfortably.

The table, by interval length

As in matrix chain, the sub-intervals a cell needs are always shorter than the cell itself, but their endpoints do not move monotonically. So iterate by length, shortest first:

python
def max_coins(nums):
    balloons = [1] + nums + [1]
    n = len(balloons)
    dp = [[0] * n for _ in range(n)]

    for length in range(2, n):              # distance between the open boundaries
        for i in range(0, n - length):
            j = i + length
            for k in range(i + 1, j):
                dp[i][j] = max(dp[i][j],
                               dp[i][k] + dp[k][j]
                               + balloons[i] * balloons[k] * balloons[j])

    return dp[0][n - 1]
Crucial Notein the recurrence, k is the balloon burst last, not first, and the two recursive calls f(i, k) and f(k, j) both keep k as an endpoint — it is a standing wall in both, not a member of either. If you find yourself writing f(i, k-1) and f(k+1, j), you have slipped back into the inclusive-range habit from other interval problems and the neighbour arithmetic will come out wrong.
Worked Example:nums = [3, 1, 5, 8]
Padded: [1, 3, 1, 5, 8, 1], indices 0 to 5.

Working up by interval length, the small ranges are straightforward — for example f(0, 2) has only k = 1 available, earning 1 × 3 × 1 = 3. Skipping to the finished answer, the optimal order the table discovers is:

- Burst the 1 (value 1) first, with neighbours 3 and 5: earns 3 × 1 × 5 = 15. Array becomes [3, 5, 8].
- Burst the 5, with neighbours 3 and 8: earns 3 × 5 × 8 = 120. Array becomes [3, 8].
- Burst the 3, with a padded 1 on the left and 8 on the right: earns 1 × 3 × 8 = 24. Array becomes [8].
- Burst the 8, with padding on both sides: earns 1 × 8 × 1 = 8.

Total 15 + 120 + 24 + 8 = 167.

Read that in reverse and you can see the recurrence's view: the balloon burst last over the whole range was the 8, and everything to its left was cleared first while the 8 stood as a wall.

A small case worth checking by hand: nums = [1, 5], padded to [1, 1, 5, 1]. Burst the 1 first for 1 × 1 × 5 = 5, then the 5 for 1 × 5 × 1 = 5, totalling 10. The other order gives 1 × 5 × 1 = 5 then 1 × 1 × 1 = 1, totalling 6. So the answer is 10, and the greedy instinct to burst the biggest balloon first is wrong — big balloons are worth more as neighbours than as targets, so you generally want them alive as long as possible.

What this problem is really teaching

Every other problem in this section had an obvious direction of progress: the next step, the next index, the next day. This one does not, and the skill being tested is what to do when that is the case.

The recipe: if fixing the first move leaves a mess, fix the last one. The test for whether you have chosen well is always the same — does the remaining problem break into independent pieces of the same kind? Here, choosing the last balloon in a range left two sides permanently separated by a standing wall. Choosing the first left two sides that immediately merged.

The second lesson is about the padding. Adding sentinel 1s at the ends turned a rule with special cases into plain arithmetic. Look for that move whenever a problem's edges behave differently from its middle: an identity element at the boundary (1 for products, 0 for sums, infinity for minima) usually erases the special case entirely, and erased special cases cannot contain bugs.

Finally, note how the greedy instinct inverted here. Normally you grab the big prize first; here the big values are most valuable while they are still standing, because they multiply their neighbours' payoffs. Whenever an element's value depends on its context rather than on itself, expect greedy reasoning to fail and expect the order of operations to be the real problem.

Exponential Try Every Order
→
O(N³) Time · O(N²) Space Interval Table on Last Burst