Burst Balloons

Burst Balloons is the classic hard interval-DP problem. It looks like a greedy puzzle, but the winning move is to flip the question around: instead of asking which balloon to burst first, ask which one to burst last.

The slow way first

The tempting move is to try bursting balloons one at a time and recurse on what is left. But when you burst a balloon "first," its two neighbors merge — so the score of every remaining balloon now depends on the order of past bursts. The subproblems overlap in a tangled way and there is no clean state to memoize. Brute-forcing all orders is O(n!) — hopeless.

The question to ask: what choice leaves two clean, independent subproblems? Bursting first does not. Bursting last does.

The idea: pick the last balloon to burst

First pad the array with a 1 on each end: pad = [1] + nums + [1]. Now consider an interval (l, r) of balloons. Suppose balloon k is the last one we burst inside it. By the time it pops, everything else in (l, r) is gone, so its only neighbors are the fixed boundaries pad[l-1] and pad[r+1]. That burst earns pad[l-1] * pad[k] * pad[r+1], and the two sides (l, k-1) and (k+1, r) are now independent subproblems.

So dp[l][r] = max over k of pad[l-1]*pad[k]*pad[r+1] + dp[l][k-1] + dp[k+1][r]. We fill the table by interval length so every smaller interval is ready before the one that needs it.

Walk through it

Step through the animation. The dp triangle fills diagonal by diagonal: length-1 intervals first (a single balloon between its two boundaries), then length 2, 3, and finally the full range (1, 4). Each cell tries every k as the last burst and keeps the max. The top-right cell dp[1][4] is the final answer: 167.

Pseudocode

pad = [1] + nums + [1]
dp = (n x n) table of zeros
for length from 1 to number of balloons:
    for each interval (l, r) of that length:
        for each balloon k in l..r:
            gain = pad[l-1] * pad[k] * pad[r+1]   # k is burst LAST
            total = gain + dp[l][k-1] + dp[k+1][r]
            dp[l][r] = max(dp[l][r], total)
return dp[1][n-2]                                  # whole padded range

The Python solution

def max_coins(nums):
    pad = [1] + nums + [1]
    n = len(pad)
    dp = [[0] * n for _ in range(n)]
    for length in range(1, n - 1):
        for l in range(1, n - length):
            r = l + length - 1
            for k in range(l, r + 1):
                gain = pad[l - 1] * pad[k] * pad[r + 1]
                total = gain + dp[l][k - 1] + dp[k + 1][r]
                dp[l][r] = max(dp[l][r], total)
    return dp[1][n - 2]

• pad adds the imaginary 1 boundaries so we never index out of bounds.
• The outer length loop guarantees both dp[l][k-1] and dp[k+1][r] are already computed.
• gain is the coins from bursting k last, when its neighbors are exactly the fixed boundaries.
• Lines 9-11 are the heart: try each k as the last burst and keep the best total.
• dp[1][n-2] covers the original (unpadded) array — the answer.

Complexity

The O(n²) table holds one entry per interval, and filling each entry scans up to n candidates for k, giving O(n³).

When this pattern shows up

Practice