Burst Balloons

LeetCode 312 (Burst Balloons) is the problem that teaches you when forward recurrence-thinking fails and backward thinking is the only way out. You are given n balloons in a row, each labeled with an integer nums[i]. Two phantom balloons of value 1 sit at the boundaries. You burst the balloons in some order; bursting balloon i earns nums[left] · nums[i] · nums[right] coins, where nums[left] and nums[right] are the values of the currently adjacent balloons (the original neighbors of i, or whatever survives after earlier pops have collapsed the row). Maximize total coins. Naïve n! brute force is intractable for n > 10. The intended solution is interval DP — but the obvious “decide which balloon to pop first” formulation has non-overlapping sub-problems and does not memoize. The trick is to reverse the question: for each interval, which balloon is popped last? That balloon’s neighbors at popping time are the boundary balloons of the interval (untouched until the very end), making the subproblems decoupled and the recurrence local. The result is a clean O(n³) interval DP, structurally identical to Matrix Chain Multiplication but reading the “merge” step in reverse.

1. Intuition — “Why Forward Thinking Fails”

The natural first attempt is forward: pick balloon k to pop first, earn nums[-1] · nums[k] · nums[k+1] (with -1 and n indexing into the phantom 1’s), then recurse on the remaining n-1 balloons. The problem is that the remaining balloons are no longer in the original positions. After popping k, the balloons at positions k-1 and k+1 become adjacent — their cost when they are eventually popped depends on this new adjacency, which depends on the order of all the other pops. The subproblem is no longer “pop the balloons in this contiguous range” — it is “pop the balloons in this non-contiguous union of ranges with stitched boundaries,” and that union depends on the popping history.

Concretely: after popping k from [0, n-1], the residual problem is [0, k-1] ∪ [k+1, n-1] with the seam between them having a special property — nums[k-1] and nums[k+1] are now neighbors. This stitching means the left subproblem and right subproblem are not independent. Whatever you do in the left half affects the cost of bursting balloons in the right half (because the right half’s leftmost survivor will be adjacent to the left half’s rightmost survivor, possibly years later in the popping order). A DP whose subproblems share state cannot be memoized cleanly — the state space becomes the full 2^n set of “balloons not yet popped.”

This is the lesson of LC 312: forward DP only works when each step leaves a clean residue independent of the step’s details. In Burst Balloons, popping a balloon changes the adjacency of the balloons around it, breaking independence.

The fix — and it is genuinely clever — is to invert the question. Instead of “which balloon do I pop first?” ask “in this interval, which balloon do I pop last?” A different, decisive reframing: as long as that “last” balloon hasn’t been popped yet, it stands as a wall protecting the interval’s two endpoints from being touched. The two endpoints (the balloon just outside the interval on the left and on the right) are precisely the ones we treat as untouched in the recurrence’s neighbor lookup. Once the last balloon is popped, its neighbors at popping time are exactly those two endpoints — because everything strictly between them inside the interval has already been popped.

This reframing makes subproblems truly independent. The interval (i, j) with both endpoints i and j themselves not yet popped is a self-contained problem. We pick a “last” balloon k ∈ (i, j). Before k is popped, the sub-intervals (i, k) and (k, j) are popped first, each independently — neither sub-interval can affect the other because k itself is the wall between them. When k is finally popped, its neighbors are exactly nums[i] and nums[j] (the interval’s endpoints), because nothing else inside is left.

The reversal of “first” to “last” is the kind of substitution that, once seen, looks obvious. Without it, this problem is exponentially hard. With it, it is a textbook O(n³) DP. This is the most-cited example in interview prep material of why state design is the hardest part of DP — the recurrence is mechanical once the state is right; the state is unobtainable without the reversal trick.

2. Why “First” Fails — A Concrete Counterexample

Let nums = [3, 1, 5, 8] (with phantom 1’s at indices -1 and 4).

Forward attempt: define f(S) = max coins burstable on the surviving multiset S. Pop choice for the first burst is one of {3, 1, 5, 8} at original positions {0, 1, 2, 3}. If we pop balloon at position 1 first (value 1), we earn 3 · 1 · 5 = 15 and the residue is [3, 5, 8] — but now in the residue, balloon 3 is adjacent to balloon 5, even though originally they weren’t. The “state” [3, 5, 8] is not a contiguous slice of the input; it is a stitched union with a memory of which balloons popped before. To memoize this honestly, the cache key must encode which subset of original balloons is still alive, which has 2^n possible values. With n = 300 (a typical LC constraint), 2^300 is ≈ 10^90. Not a thing.

You might object: can’t we still represent the subset as a bitmask and memoize? Yes, but 2^n is exponential. This works only for n ≲ 20 (bitmask DP, see future Bitmask DP note). LC 312 wants n up to a few hundred — bitmask is out.

Backward attempt: define dp(i, j) = max coins poppable on the open interval (i, j) (balloons strictly between indices i and j, with i and j themselves unpopped and serving as boundary walls). The state is just (i, j) — O(n²) distinct states, indexed by integers. Transition picks a “last popper” k ∈ (i, j):

dp(i, j) = max over k in (i, j) of:
              dp(i, k) + dp(k, j) + nums[i] · nums[k] · nums[j]

The cost nums[i] · nums[k] · nums[j] is what k earns when it is popped last in (i, j): at that moment, everything strictly between i and j (other than k) has already been popped, so k’s neighbors are nums[i] and nums[j] — the interval’s untouched endpoints. The two sub-intervals (i, k) and (k, j) are independent: each is solved in isolation because k is the wall between them.

This recurrence is structurally identical to Matrix Chain Multiplication, just with max instead of min and a slightly different cost term. Both are interval DPs; both have O(n³) complexity; both have the same length-outer / i-inner / j-derived loop signature.

3. Tiny Worked Example

Let nums = [3, 1, 5, 8]. Pad with phantom 1’s: the working array is padded = [1, 3, 1, 5, 8, 1] of length n + 2 = 6, indexed 0..5. The original balloons sit at indices 1..4.

State: dp[i][j] = max coins from popping every balloon strictly between indices i and j of padded, with padded[i] and padded[j] themselves unpopped. We want dp[0][5].

Recurrence (for j > i + 1):

dp[i][j] = max over k in (i+1, j-1) of:
              dp[i][k] + dp[k][j] + padded[i] · padded[k] · padded[j]

Base case: dp[i][j] = 0 whenever j - i < 2 (no balloons strictly between).

Iteration order: length-outer. Same signature as MCM. The interval length j − i ranges from 2 (the smallest non-trivial interval — exactly one balloon inside) up to n + 1.

Let’s fill the table. We use the padded array.

padded = [1, 3, 1, 5, 8, 1] (indices 0..5).

Length 2 (one balloon strictly inside):

• dp[0][2]: k = 1. Cost = 0 + 0 + 1·3·1 = 3.
• dp[1][3]: k = 2. Cost = 0 + 0 + 3·1·5 = 15.
• dp[2][4]: k = 3. Cost = 0 + 0 + 1·5·8 = 40.
• dp[3][5]: k = 4. Cost = 0 + 0 + 5·8·1 = 40.

	j=0	j=1	j=2	j=3	j=4	j=5
i=0	0	0	3
i=1		0	0	15
i=2			0	0	40
i=3				0	0	40
i=4					0	0
i=5						0

Length 3 (two balloons strictly inside):

• dp[0][3]: k ∈ {1, 2}.
  • k=1: dp[0][1] + dp[1][3] + 1·3·5 = 0 + 15 + 15 = 30.
  • k=2: dp[0][2] + dp[2][3] + 1·1·5 = 3 + 0 + 5 = 8.
  • Max: 30 at k=1.
• dp[1][4]: k ∈ {2, 3}.
  • k=2: dp[1][2] + dp[2][4] + 3·1·8 = 0 + 40 + 24 = 64.
  • k=3: dp[1][3] + dp[3][4] + 3·5·8 = 15 + 0 + 120 = 135.
  • Max: 135 at k=3.
• dp[2][5]: k ∈ {3, 4}.
  • k=3: dp[2][3] + dp[3][5] + 1·5·1 = 0 + 40 + 5 = 45.
  • k=4: dp[2][4] + dp[4][5] + 1·8·1 = 40 + 0 + 8 = 48.
  • Max: 48 at k=4.

	j=0	j=1	j=2	j=3	j=4	j=5
i=0	0	0	3	30
i=1		0	0	15	135
i=2			0	0	40	48
i=3				0	0	40
i=4					0	0
i=5						0

Length 4 (three balloons strictly inside):

• dp[0][4]: k ∈ {1, 2, 3}.
  • k=1: dp[0][1] + dp[1][4] + 1·3·8 = 0 + 135 + 24 = 159.
  • k=2: dp[0][2] + dp[2][4] + 1·1·8 = 3 + 40 + 8 = 51.
  • k=3: dp[0][3] + dp[3][4] + 1·5·8 = 30 + 0 + 40 = 70.
  • Max: 159 at k=1.
• dp[1][5]: k ∈ {2, 3, 4}.
  • k=2: dp[1][2] + dp[2][5] + 3·1·1 = 0 + 48 + 3 = 51.
  • k=3: dp[1][3] + dp[3][5] + 3·5·1 = 15 + 40 + 15 = 70.
  • k=4: dp[1][4] + dp[4][5] + 3·8·1 = 135 + 0 + 24 = 159.
  • Max: 159 at k=4.

	j=0	j=1	j=2	j=3	j=4	j=5
i=0	0	0	3	30	159
i=1		0	0	15	135	159
i=2			0	0	40	48
i=3				0	0	40
i=4					0	0
i=5						0

Length 5 (the full original interval):

• dp[0][5]: k ∈ {1, 2, 3, 4}.
  • k=1: dp[0][1] + dp[1][5] + 1·3·1 = 0 + 159 + 3 = 162.
  • k=2: dp[0][2] + dp[2][5] + 1·1·1 = 3 + 48 + 1 = 52.
  • k=3: dp[0][3] + dp[3][5] + 1·5·1 = 30 + 40 + 5 = 75.
  • k=4: dp[0][4] + dp[4][5] + 1·8·1 = 159 + 0 + 8 = 167.
  • Max: 167 at k=4.

Answer: dp[0][5] = 167. This matches the LeetCode 312 example output for nums = [3, 1, 5, 8].

Reading the optimal popping order from the splits: at the top level, balloon 4 (value 8, original index 3) is popped last. Before that, the sub-interval (0, 4) is solved with k=1 (balloon at original index 0, value 3) popped last in the left sub-problem; the sub-sub-interval (1, 4) has k=3 (balloon at original index 2, value 5) popped last; and (1, 3) has k=2 (balloon at original index 1, value 1) popped last. Reading these in reverse order of “popped last” gives the actual popping sequence: 1, 5, 3, 8 (values), which costs 3·1·5 + 3·5·8 + 1·3·8 + 1·8·1 = 15 + 120 + 24 + 8 = 167. ✓

4. Pseudocode

max_coins(nums):
    padded := [1] + nums + [1]                       # length n+2, index 0..n+1
    n := length(padded) - 2
    dp := 2D array of size (n+2) × (n+2), init 0
    for length := 2 to n + 1:                        # interval length, OUTER
        for i := 0 to n + 1 - length:
            j := i + length
            for k := i + 1 to j - 1:                 # k is the LAST balloon popped in (i, j)
                cost := dp[i][k] + dp[k][j] + padded[i] * padded[k] * padded[j]
                if cost > dp[i][j]:
                    dp[i][j] := cost
    return dp[0][n + 1]

The outer loop iterates length; i is derived; j = i + length is derived; k ranges over the strict interior. This is the interval-DP loop signature from Matrix Chain Multiplication.

5. Python Implementation

5.1 Bottom-Up Tabulation

def max_coins(nums: list[int]) -> int:
    padded = [1] + nums + [1]
    n = len(padded) - 2                              # original count of balloons
    # dp[i][j] for 0 <= i < j <= n+1; meaningful only when j - i >= 2
    dp = [[0] * (n + 2) for _ in range(n + 2)]
 
    for length in range(2, n + 2):                   # interval length from 2 to n+1
        for i in range(0, n + 2 - length):
            j = i + length
            best = 0
            for k in range(i + 1, j):
                cost = dp[i][k] + dp[k][j] + padded[i] * padded[k] * padded[j]
                if cost > best:
                    best = cost
            dp[i][j] = best
 
    return dp[0][n + 1]

5.2 Top-Down Memoization

from functools import lru_cache
 
def max_coins_memo(nums: list[int]) -> int:
    padded = [1] + nums + [1]
 
    @lru_cache(maxsize=None)
    def helper(i: int, j: int) -> int:
        if j - i < 2:
            return 0
        return max(
            helper(i, k) + helper(k, j) + padded[i] * padded[k] * padded[j]
            for k in range(i + 1, j)
        )
 
    return helper(0, len(padded) - 1)

The top-down version is the easier sell when explaining to a colleague: the recursion exactly mirrors the “pick the last balloon” English description. As with Matrix Chain Multiplication, top-down avoids the iteration-order trap (recursion always evaluates the smaller intervals first).

5.3 Reconstruction — Recovering the Popping Order

If you also want the actual order of bursts, record the optimal k at each cell:

def max_coins_with_order(nums: list[int]) -> tuple[int, list[int]]:
    padded = [1] + nums + [1]
    n = len(padded) - 2
    dp = [[0] * (n + 2) for _ in range(n + 2)]
    last = [[0] * (n + 2) for _ in range(n + 2)]
 
    for length in range(2, n + 2):
        for i in range(0, n + 2 - length):
            j = i + length
            for k in range(i + 1, j):
                cost = dp[i][k] + dp[k][j] + padded[i] * padded[k] * padded[j]
                if cost > dp[i][j]:
                    dp[i][j] = cost
                    last[i][j] = k
 
    order: list[int] = []
    def recover(i: int, j: int) -> None:
        if j - i < 2:
            return
        k = last[i][j]
        recover(i, k)
        recover(k, j)
        order.append(k - 1)                          # convert padded index back to original
    recover(0, n + 1)
    # `order` lists the popped indices; the LAST element is the FINAL pop in original input
    return dp[0][n + 1], order

The recursion is post-order: the sub-intervals are popped before k itself. Reading the resulting list left-to-right gives the popping order in execution order.

6. Complexity

Time: O(n³). O(n²) cells, each minimized over O(n) split points.

Space: O(n²) for the DP table; another O(n²) for the last reconstruction table if needed. This cannot be reduced asymptotically — every cell dp[i][j] is read by O(n) larger cells dp[i'][j'] with i' ≤ i ≤ j ≤ j', so all O(n²) cells must be stored.

Brute force for comparison. All popping orders: n!. For n = 100 (a typical LC limit), 100! ≈ 10^158. The DP at n = 100 does ≈ 10^6 operations. The reframing trick takes the problem from “computationally hopeless” to “trivially fast.”

Why no further speedup is known. The Knuth-Yao quadrangle-inequality speedup that improves Matrix Chain Multiplication to O(n²) for cost functions satisfying the QI does not directly apply here because the cost padded[i] · padded[k] · padded[j] does not, in general, satisfy the relevant monotonicity. There may be specific instance classes with faster algorithms, but O(n³) is the standard — every editorial and reference implementation surveyed treats O(n²) cells × O(n) split-point loop as canonical (per the algo.monster walkthrough and the doocs/leetcode reference editorial). No sub-cubic algorithm for the general-input variant has been published. With the LC constraint n ≤ 300, the 27 · 10⁶-operation table fits comfortably under the time limit, so there is no practical pressure for a faster algorithm even if one existed.

7. Variants and Related Problems

7.1 Matrix Chain Multiplication

Burst Balloons’ twin. Both pick a “split / pivot point” inside an interval. MCM minimizes; Burst Balloons maximizes. MCM’s cost term is p[i-1] · p[k] · p[j] (left rows × shared dim × right cols); Burst Balloons’ is padded[i] · padded[k] · padded[j] (left endpoint × popper × right endpoint). Both are O(n³) interval DP.

7.2 Minimum Cost to Merge Stones (LC 1000)

Same interval-DP family with merge arity > 2 (you can only merge K adjacent piles at once, not 2). Adds a third dimension or a careful loop-structure modification.

7.3 Remove Boxes (LC 546)

Looks like Burst Balloons but is harder: removing a contiguous run of same-colored boxes earns count². Requires an extra dimension in the DP state — dp[i][j][k] where k tracks “how many boxes of color boxes[i] are stuck to the left edge that we will eventually merge in.” Three dimensions, O(n^4) time. Beautiful problem; harder than Burst Balloons by a step.

7.4 Strange Printer (LC 664)

Print a string with a printer that prints contiguous same-character runs. Minimum number of turns. Interval DP with character-continuation logic.

7.5 Palindrome Partitioning II (LC 132)

Min cuts to partition string into palindromes. Uses Palindromic Substrings as a sub-routine; cuts DP is then 1D over indices.

7.6 Optimal Triangulation of a Convex Polygon

Same DP as Matrix Chain. Each triangulation choice picks a third vertex (the analog of the split / pivot).

8. Diagram — The “Last Balloon” Reframing

flowchart LR
    L["dp i, k<br/>solve OPEN interval (i, k)<br/>i, k both unpopped"] --> R[combine]
    R2["dp k, j<br/>solve OPEN interval (k, j)<br/>k, j both unpopped"] --> R
    M["k pops LAST<br/>cost: nums i × nums k × nums j"] --> R
    R --> ANS["dp i, j<br/>= max over k"]

What this diagram shows. To compute dp[i][j] (max coins on the open interval (i, j)), we pick a “last balloon” k ∈ (i, j). The two sub-intervals (i, k) and (k, j) are solved independently — neither subproblem is allowed to touch k (its position is the wall), and once both are done the only remaining balloon is k itself. When k finally pops, its neighbors are nums[i] and nums[j] (the interval’s untouched endpoints — because everything strictly between has already been popped). The cost of that final pop is nums[i] · nums[k] · nums[j]. We take the maximum over all choices of k. The crucial visual is the wall property of k: it stands between the two sub-intervals as a guarantor of independence. Forward DP fails because no such wall exists when picking the first balloon to pop — popping the first removes the wall between two halves rather than maintaining it.

9. Common Interview Problems

Problem	LeetCode #	Pattern
Burst Balloons	LC 312	The “think backward” interval DP
Matrix Chain Multiplication	(CLRS 15.2)	Interval DP twin, minimization
Minimum Cost to Merge Stones	LC 1000	Interval DP, K-way merge constraint
Remove Boxes	LC 546	3D interval DP, boxes-stuck dimension
Strange Printer	LC 664	Interval DP, character-continuation
Minimum Score Triangulation of Polygon	LC 1039	Interval DP, geometric formulation
Allocate Mailboxes	LC 1478	Partitioning DP with interval cost
Cherry Pickup II	LC 1463	3D path DP — different, but “pair of trajectories” idea is structurally similar to “left and right pop sequences”

The Burst Balloons reframing trick — “think about which thing happens last, not which happens first” — recurs in tournament-style DPs, optimal binary tree DPs, and many post-order tree problems.

10. Pitfalls

10.1 Forgetting the Phantom 1’s

The boundary balloons (value 1 each) are essential. Without them, the k = 0 and k = n − 1 cases have no left/right neighbor, and the formula becomes ambiguous. Padding both ends with 1 makes the recurrence uniform. Forgetting this padding is the most common typo bug in LC 312.

10.2 Forward DP Trap

If you start writing dp[mask] = max coins burstable from this set of survivors, you have fallen into the bitmask trap. Stop. Reread the problem; re-derive with backward thinking. Bitmask DP works but is exponential in n and only viable for n ≤ 20-ish.

10.3 Wrong Iteration Order (Length Outer)

Same as Matrix Chain Multiplication: the canonical loop is for length: for i: j = i + length: for k. Filling dp row-by-row reads dp[k][j] where k > i, i.e., a later row that has not yet been computed (and the cell holds 0, leading to wrong answers). The length-outer fill order is non-negotiable.

10.4 Closed vs Open Interval Confusion

dp[i][j] represents the open interval (i, j) (balloons strictly between, exclusive of endpoints). Some implementations use closed intervals [i, j] (balloons inclusive of endpoints). Both work, but mid-stream switches cause off-by-one bugs in the cost term and the loop bounds. Pin one convention at the top of your code. The open-interval convention is slightly cleaner because padded[i] and padded[j] directly give the endpoint walls.

10.5 Computing the Cost Using Original Indices

If you keep nums (length n, no padding) and try to write nums[i] · nums[k] · nums[j] directly, the boundary cases break (no nums[-1] or nums[n]). The cleaner approach is to pad explicitly and operate on padded throughout. The reverse direction — preserving original indices and using “if i < 0: … else: …” conditionals — works but is bug-prone.

10.6 Neighbor Update During Pop

A reflexive but wrong implementation: maintain a current_neighbors array, update it on each pop, recompute costs. This does simulate the problem correctly but only for one fixed popping order — it gives no help in finding the optimal order. Brute-forcing over all permutations and simulating each is O(n · n!).

10.7 Off-By-One in Padding Length

Padding makes padded of length n + 2. The valid open intervals have 0 ≤ i < j ≤ n + 1. The answer is dp[0][n + 1] — not dp[1][n] or dp[0][n]. This off-by-one is easy to introduce and produces a wrong answer that is, frustratingly, often plausible (within a small factor of the correct value).

10.8 Assuming the Last-to-Pop Order Is Greedy

A natural-but-wrong heuristic: always pop the smallest-value balloon last (so the final pop costs less). This gives wrong answers — the example nums = [3, 1, 5, 8] has 8 as the last balloon popped, despite being the largest. The sub-intervals’ costs interact in non-monotone ways; only the DP gets the right answer.

10.9 Integer Overflow in Other Languages

The LeetCode 312 constraints are 1 ≤ n ≤ 300 and 0 ≤ nums[i] ≤ 100 (per the problem statement mirrored on doocs/leetcode). The product of three balloon values is ≤ 10⁶. Summed over at most 300 bursts the total is ≤ 3 × 10⁸ — well within 32-bit signed int range (~2.1 × 10⁹). For variant problems with larger value ranges or longer arrays, switch to 64-bit (long in Java, int64 in Go) defensively.

10.10 Confusing “Last to Pop” With “First to Pop in Sub-Interval”

The “last popped in (i, j)” balloon is the first one selected when reading the interval’s recurrence top-down — but it is the last one to actually burst chronologically. The reversal between recursion order and popping order is dizzying when first encountered. Internalize: the recursion picks the last burst; the actual burst sequence is reconstructed in reverse of the recursion’s choice order.

10.11 Boundary Case n = 0

If nums is empty, padded = [1, 1] and the answer is dp[0][1] = 0 (no balloons to pop). The DP handles this naturally, but defensive code with if not nums: return 0 is cleaner.

10.12 Memoization Cache Key

Memoize on (i, j) (integers). Don’t memoize on the surviving multiset; that takes you back to bitmask DP, which is exponential.

11. Open Questions

• Is there a sub-O(n³) algorithm? No publication I have found beats O(n³) for general inputs. Specific instance classes (monotone nums, unimodal nums) might admit faster solutions.
• How is the reframing trick generalized? The principle “decide what happens last rather than what happens first” appears in optimal-merge problems, tournament-bracket DPs, and Huffman-style greedy proofs. There is a folklore name for this trick — sometimes “think about the last operation,” sometimes “consider the root of the parse tree” — but no single canonical reference.
• Why does this work for bursting but not for analogous insertion problems? Because the insertion analog can be similarly recast — every insertion has a first one, and that first one’s neighbors are the (untouched) initial endpoints. The trick is symmetric; for some problems “last” is natural, for others “first” is. Recognizing which is the substantive skill.
• Does the related “stick-cutting” problem (cut a stick into pieces with prescribed cut points; cost of each cut = current stick length) fit the same DP? Yes — it is essentially MCM with a different cost function. CLRS exercise 15-9.

12. See Also

• Matrix Chain Multiplication — the interval-DP twin
• Memoization vs Tabulation — top-down avoids the iteration-order trap
• DP State Identification — the reframing trick is the textbook example of state design mattering more than recurrence design
• Palindromic Substrings — interval DP for palindrome detection
• Tree Diameter — post-order tree DP, conceptually similar “combine sub-results at a chosen pivot”
• Big-O Notation — discussion of O(n³) interval DP and n! brute force
• SWE Interview Preparation MOC