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. Fixing the last event leaves independent pieces; fixing the first does not.
The state, as a story

Take a stretch of balloons and imagine I'm going to burst all of them while everything outside the stretch stays intact. Some balloon in that stretch is burst last — call it k.

Why look at the last one? At the moment k bursts, every other balloon in the stretch is already gone, so k's two neighbours are whatever sits just outside the stretch — fixed values that don't depend on the order I used inside. So bursting k last always earns nums[left] × nums[k] × nums[right].

And before that: the balloons on k's left were all burst with k still standing as their right wall, and the balloons on k's right were all burst with k still standing as their left wall. The two sides never touch, because k sits between them until the very end. Two independent subproblems of the same kind. (Burst k first and the two sides merge instantly — that is why last, not first.)

To keep the boundary arithmetic clean, I use an open range: f(i, j) looks at the balloons strictly between i and j, with i and j themselves still standing as the walls.

State Definitionf(i, j) is the most coins from bursting every balloon strictly inside (i, j), with balloons i and j still there.

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, then recursion

A missing neighbour counts as 1. Rather than write boundary checks everywhere, pad the array with a 1 at each end. Multiplying by 1 changes nothing, so every real balloon now has a genuine neighbour on both sides.

Write the story as plain recursion — try every balloon as the last one in the range:

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

    def f(i, j):
        if j <= i + 1: return 0                   # nothing strictly between
        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)
        return best

    return f(0, n - 1)                            # everything between the two padded 1s

Correct, but it re-solves the same ranges many times over. There are only about N² different (i, j) ranges, so keep a notebook:

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

    def f(i, j):
        if j <= i + 1: return 0
        if (i, j) in memo: return memo[(i, j)]
        best = 0
        for k in range(i + 1, j):
            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 table, from the recurrence

Let dp[i][j] hold what f(i, j) returned, and swap each call for an array read:

dp[i][j] = max over k of [ dp[i][k] + dp[k][j] + balloons[i] × balloons[k] × balloons[j] ]

Every sub-range a cell needs is shorter than the cell itself, but the endpoints don't move in one direction. What always shrinks is the range length, so loop by length, shortest first. The base (adjacent walls, nothing between) is already 0 from the array init, and the answer is dp[0][n-1]:

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