Burst Balloons (LeetCode 312)

The problem

Balloons in a row each carry a number. Bursting balloon i earns left × nums[i] × right coins, where left and right are its current neighbours (balloons that have not been burst yet). Past either end, treat the neighbour as a 1. Burst every balloon and return the most coins possible.

Input:  nums = [3, 1, 5, 8]
Output: 167

Burst 1, then 5, then 3, then 8: 3·1·5 + 3·5·8 + 1·3·8 + 1·8·1 = 15 + 120 + 24 + 8 = 167.

How to think about it

Start with brute force. Try every order of bursting: n! orders. For n = 300 that is hopeless.

Why “first burst” doesn’t split cleanly. If you pick the balloon to burst first, its two sides become neighbours of each other afterwards. The left and right parts are no longer independent, so you cannot solve them separately.

The key insight: pick the balloon that bursts last. Pad the array with a 1 at each end: a = [1] + nums + [1]. In an open range (l, r), suppose balloon m is the last one burst. Then while everything else in (l, m) and (m, r) is being burst, m is still there, acting as a wall. The two sides really are independent. And when m finally goes, its neighbours are exactly a[l] and a[r]. So:

dp[l][r] = max over l < m < r of dp[l][m] + a[l]·a[m]·a[r] + dp[m][r]

Fill short ranges first. dp[l][r] needs smaller ranges inside it, so loop over range length from small to large.

Which pattern is this? Interval DP. The tell is “the cost of an action depends on its neighbours, which change as you go”: think about the last action in a range so the boundaries stay fixed.

Approach

1. Build a = [1] + nums + [1], with n = len(a).
2. Create an n × n table of zeros. dp[l][r] is the best for bursting everything strictly between l and r. Adjacent l, r hold nothing, so 0.
3. For length from 2 up to n - 1, for each l, set r = l + length.
4. Try every m strictly between them as the last balloon, and keep the max of the formula.
5. Return dp[0][n - 1].

Solution

def maxCoins(nums):
    a = [1] + nums + [1]; n = len(a)                 # virtual 1s at both ends
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):                       # shorter ranges first
        for l in range(n - length):
            r = l + length
            for m in range(l + 1, r):                # m = balloon burst LAST in (l, r)
                dp[l][r] = max(dp[l][r], dp[l][m] + a[l]*a[m]*a[r] + dp[m][r])
    return dp[0][n - 1]
# maxCoins([3,1,5,8]) -> 167

Dry run

a = [1, 3, 1, 5, 8, 1]. Each row is one open range (l, r), the balloons inside, which one is best to burst last, and dp[l][r].

The full range bursts 8 last: dp[0][4] + 1·8·1 + dp[4][5] = 159 + 8 + 0 = 167.

Complexity

• Time: O(n³). There are O(n²) ranges, and each tries O(n) split points.
• Space: O(n²). For the table.

Edge cases and pitfalls

• Empty input returns 0: a = [1, 1] and the loops never run.
• One balloon gives 1 × x × 1 = x.
• Zeros are fine. A 0 balloon earns nothing itself and zeroes any product it’s a neighbour in, which the DP accounts for.
• Thinking “burst first” leads to a recurrence whose sub-problems aren’t independent. This is the classic trap.
• Wrong loop order. Iterating l and r in plain index order reads ranges that aren’t filled yet. Loop over length first.

Related problems

• Minimum Cost to Cut a Stick (LeetCode 1547): the same “split a range at a middle point” interval DP.
• Stone Game (LeetCode 877): interval DP where you shrink a range from its ends.
• Longest Palindromic Subsequence (LeetCode 516): another dp[i][j] filled by increasing length.