Burst Balloons, in depth: the last-burst reframe, interval DP with reconstruction, and why greedy and Knuth fail

Why the obvious approaches fail

Brute force tries every order: n! of them, so 10 balloons already means 3.6 million simulations. Dynamic programming needs a subproblem whose answer does not depend on anything outside it. The natural attempt is to choose the first balloon to burst and recurse on the two sides. That fails: after bursting k, its old neighbours k-1 and k+1 become adjacent, so the coins earned on the left side depend on what is still standing on the right. The two halves are not independent, and the state would have to record which balloons survive, which is exponential.

Greedy rules fail too. Bursting the smallest value first looks plausible because it keeps large values around as multipliers. On [3, 1, 5, 8] it scores 78 against an optimum of 167, and on 2,000 random arrays of 1 to 6 values between 1 and 9 it disagreed with the exhaustive optimum 1,076 times.

The reframe: which balloon goes last?

Turn the question around: which balloon in a range is burst last? Pad the array with a 1 at each end, giving a[0..n+1]. Define dp[i][j] as the best total from bursting every balloon strictly between positions i and j, while i and j themselves are still standing. If k is the last balloon burst in that open interval, then while the balloons between i and k are being burst, k is still present and acts as a fixed wall; the same holds on the k-to-j side. The two sides are now genuinely independent, and when k finally goes its neighbours are exactly i and j:

dp[i][j] = max over i < k < j of  dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]
dp[i][i+1] = 0   (no balloons strictly between adjacent walls)
answer = dp[0][n+1]

This is the same shape as matrix-chain multiplication, where k is the last split, and the matrix chain article shows the parenthesisation version of the argument. Both fill the table by increasing interval length so that every dp[i][k] and dp[k][j] is ready before dp[i][j] needs it.

Bottom-up code with reconstruction

def max_coins(nums):
    a = [1] + list(nums) + [1]
    n = len(a)
    dp = [[0] * n for _ in range(n)]
    choice = [[-1] * n for _ in range(n)]
    for length in range(2, n):            # distance between the two walls
        for i in range(0, n - length):
            j = i + length
            best, arg, walls = -1, -1, a[i] * a[j]
            for k in range(i + 1, j):     # k = last balloon burst in (i, j)
                v = dp[i][k] + dp[k][j] + walls * a[k]
                if v > best:
                    best, arg = v, k
            dp[i][j], choice[i][j] = best, arg
    return dp[0][n - 1], choice


def burst_order(choice, i, j, out):
    """Post-order: both sides of k are emptied before k itself is burst."""
    k = choice[i][j]
    if k == -1:
        return
    burst_order(choice, i, k, out)
    burst_order(choice, k, j, out)
    out.append(k - 1)                     # back to an index into nums


best, choice = max_coins([3, 1, 5, 8])
order = []
burst_order(choice, 0, 5, order)
print(best, order)                        # 167 [1, 2, 0, 3]

The order is recovered by recursing on the stored choices in post-order, because the recurrence says k is burst after everything inside (i, k) and (k, j). A common mistake is to emit k first, which replays the decisions as a first-burst order and produces a lower total. The test harness replays the reconstructed order through an independent simulator and checks that it reproduces dp[0][n+1]; on 400 random arrays of up to 7 values, both the totals and the replayed orders matched exhaustive search.

Worked example: [3, 1, 5, 8]

With [3, 1, 5, 8] the padded array is a = [1, 3, 1, 5, 8, 1]. Rows are i, columns are j, and only cells with j at least i + 2 can be non-zero:

Read some cells. dp[2][4] = 40: the only balloon between walls 1 and 8 is the 5, worth 1 x 5 x 8. dp[1][4] = 135: between the 3 and the 8 sit the 1 and the 5. Bursting the 1 last gives 0 + 40 + 3 x 1 x 8 = 64; bursting the 5 last gives dp[1][3] + 0 + 3 x 5 x 8 = 15 + 120 = 135, so the 5 goes last. At the top, dp[0][5] picks the 8 (index 4) as the very last balloon: dp[0][4] + dp[4][5] + 1 x 8 x 1 = 159 + 0 + 8 = 167.

The reconstructed order is indices [1, 2, 0, 3], values 1, 5, 3, 8. Replaying it: 3 x 1 x 5 = 15, then 3 x 5 x 8 = 120, then 1 x 3 x 8 = 24, then 1 x 8 x 1 = 8, total 167. Notice that the big values are kept until the end so they multiply each other, which no local rule discovers reliably.

One more cell: dp[0][3] = 30 covers the 3 and the 1 between walls 1 and 5. Bursting the 3 last gives 0 + dp[1][3] + 1 x 3 x 5 = 15 + 15 = 30; bursting the 1 last gives dp[0][2] + 0 + 1 x 1 x 5 = 3 + 5 = 8. When two splits do tie, the code keeps the leftmost, since it only replaces on a strictly better total; any tied choice reconstructs a valid optimal order.

Complexity, and why Knuth's speedup does not apply

The table has O(n^2) cells and each scans O(n) split points, so the algorithm is O(n^3) time and O(n^2) memory. For n = 300 that is about 4.5 million inner-loop steps; the code above took 0.56 s on CPython 3.13, and a compiled version should take tens of milliseconds at most. The memory is two 302 by 302 tables, which is small.

Interval problems sometimes allow Knuth's optimisation, which restricts the split for [i, j] to lie between the best splits for [i, j-1] and [i+1, j], cutting the work to O(n^2). It is valid only when the cost satisfies the quadrangle inequality and monotonicity, as in optimal binary search trees. Burst Balloons does not qualify, because the cost a[i] x a[k] x a[j] depends on the split itself. To check, the test harness took 3,000 random arrays of 3 to 8 values and asked whether any optimal split for [i, j] lies between the smallest optimal split of [i, j-1] and the largest of [i+1, j]. 4,474 cells violated it; one example is [4, 5, 3, 7, 4, 2, 1, 3]. Applying Knuth's trick here silently returns wrong answers, and there is no known general speedup that replaces it.

Operational guidance

• Prefer bottom-up. Memoised recursion works but reaches depth n and pays dictionary or cache overhead per cell. The loop above has no recursion except in reconstruction, whose depth is at most n.
• Keep the inner loop lean. Hoist a[i] x a[j] out of the k loop and bind dp[i] to a local name; in Python, attribute and index lookups are a large share of the runtime.
• Drop zeros first. A zero balloon earns nothing and, while standing, zeroes every product it touches, so bursting all zeros first never hurts. Removing them shrinks n before the cubic loop.
• Size the integers. With values up to 100, one burst pays at most 10^6 and 300 bursts at most 3 x 10^8, which fits in a signed 32-bit integer. Larger values need 64-bit arithmetic or Python integers.
• Return the order, not only the score. If a downstream system acts on the plan, ship the reconstruction and its replay check together.

The interval DP family

The "last operation in an interval" move is the general tool. Matrix-chain ordering, minimum-weight polygon triangulation and merging stones all fix the last split, and the palindrome partitioning article shows a related interval table used for a different cost. The reframe has limits. In Remove Boxes, removing a run of equal colours scores the square of its length, so the value of an interval depends on how many matching boxes outside it will join the final run. The state needs a third index for that count, and the cost becomes O(n^4). When the last-operation trick leaves a dependency on the outside, that is the signal to add a state dimension, not to look for a cleverer split. The dynamic programming overview places interval DP among the other state shapes.

Failure modes

• Forgetting the padding. Without the 1 walls, the boundary balloons need special cases, and off-by-one errors creep in.
• Closed instead of open intervals. If dp[i][j] includes i and j, the walls are no longer fixed and the recurrence is wrong. Keep the endpoints outside.
• Wrong fill order. Iterating i from left to right with j inside reads dp[k][j] before it is computed. Fill by length, or i descending with j ascending.
• Reconstruction in pre-order. It replays a different order with a lower score. Always replay the order through a simulator in tests.
• Assuming a speedup. Knuth's optimisation and greedy rules both fail here, as measured above.

Trade-offs

What to do next

1. Write the brute-force simulator and permutation search first; it is ten lines and it will catch every indexing mistake.
2. Implement the padded, open-interval recurrence bottom-up, then the post-order reconstruction.
3. Fuzz both against the oracle on a few hundred random arrays, replaying the reconstructed order each time.
4. Work [3, 1, 5, 8] by hand until you can explain why the 8 is burst last.
5. Solve matrix-chain ordering and polygon triangulation with the same template, then try Remove Boxes to see where a third state index becomes necessary.
6. Before using any speedup on another interval DP, test its monotonicity condition empirically the way this article did.