Lab 09 — Interval DP (Burst Balloons)

Goal

Solve Burst Balloons (LC 312) with the four-stage progression. Internalize the “think backwards” trick: instead of asking “which balloon to burst first?” (which fragments the array), ask “which balloon is burst last in the interval (i, j)?” — that balloon’s left and right neighbors are guaranteed to be nums[i] and nums[j] (the surviving boundary). After this lab you can identify and solve interval DP problems in <15 minutes.

Background Concepts

Interval DP: state dp[i][j] is the answer over the subarray (or substring) from index i to j. Recurrence iterates over a “split point” k in (i, j) and combines two sub-intervals. Defining feature: iterate by interval length ascending, so all shorter intervals are computed before they’re needed.

Burst Balloons is famous because the naive “first to burst” formulation creates non-contiguous subproblems. The “last to burst” reformulation (think backwards) restores contiguity: in interval (i, j), if k is the last balloon to burst, then by the time we burst it, all of (i, k) and (k, j) have already been burst, and k’s left and right neighbors are exactly nums[i] and nums[j] (the original boundary).

Interview Context

Burst Balloons is a top-Hard interval DP problem at Google and Microsoft. It is the problem that teaches the “think backwards” trick. Candidates who fail to recognize the contiguity issue with the forward formulation (and then naively try memoization on subsets — which is 2^N states) get stuck. Senior interviewers love this problem precisely because the reformulation is non-obvious and tests insight, not memorization.

Other interval DP problems: Matrix Chain Multiplication (LC 1547), Stone Game (LC 877), Strange Printer (LC 664), Remove Boxes (LC 546).

Problem Statement

You are given n balloons indexed 0 to n−1, each with a number nums[i] painted on it. You are asked to burst all the balloons. If you burst balloon i, you get nums[i-1] * nums[i] * nums[i+1] coins (use 1 if neighbor is out of bounds). After bursting, the neighbors become adjacent. Return the maximum coins you can collect.

Constraints

N == nums.length
1 ≤ N ≤ 500
0 ≤ nums[i] ≤ 100

Clarifying Questions

Are values non-negative? (Yes — given.)
After bursting, do neighbors become adjacent? (Yes — that’s the rule.)
What if a neighbor is out of bounds (edge balloon)? (Treat as 1.)
Must we burst all balloons? (Yes — the question asks max coins from bursting all.)
Are zero values allowed? (Yes — bursting a zero-balloon gives 0 coins.)

Examples

nums = [3, 1, 5, 8]    → 167
  Burst order: 1, 5, 3, 8.
  3 * 1 * 5 = 15;  3 * 5 * 8 = 120;  1 * 3 * 8 = 24;  1 * 8 * 1 = 8;   total 167.

nums = [1, 5]          → 10   (burst 5 → 1*5*1=5; burst 1 → 1*1*1=1; total 6.
                                Better: burst 1 first → 1*1*5=5; burst 5 → 1*5*1=5; total 10.)

nums = [9]             → 9
nums = [1]             → 1

Initial Brute Force

For each balloon, try bursting it first; recurse on the two halves. Note: this naive form has a fundamental contiguity issue — after bursting k first, the left and right halves’ boundary values change depending on which balloons remain, so the subproblems aren’t independent. We can still write it but it requires passing the current array (or the active set) down.

def burst_brute(nums):
    arr = [1] + nums + [1]
    def f(active):
        if not active: return 0
        best = 0
        for idx in range(len(active)):
            k = active[idx]
            left  = active[idx-1] if idx > 0 else 0
            right = active[idx+1] if idx+1 < len(active) else len(arr)-1
            gain = arr[left] * arr[k] * arr[right]
            best = max(best, gain + f(active[:idx] + active[idx+1:]))
        return best
    return f(list(range(1, len(arr) - 1)))

Brute Force Complexity

O(N!) — every permutation of bursts. At N=500, completely infeasible.

Optimization Path

The “first to burst” formulation cannot be memoized cleanly on (i, j) because the subproblems depend on what’s outside (i, j). Reframe: ask “in the final interval (i, j), which balloon k is burst last?”. By the time k is burst, all balloons in (i, k) and (k, j) have been burst — independently of each other. k’s neighbors at that moment are nums[i] and nums[j] (the surviving boundary). The recurrence becomes:

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

Pad nums with 1 at both ends to handle out-of-bounds neighbors uniformly. Iterate by interval length.

Final Expected Approach

1. arr = [1] + nums + [1]  (length N+2)
2. dp[i][j] = max coins from bursting all balloons strictly between i and j (boundaries i, j untouched)
3. dp[i][i+1] = 0 (no balloons between i and i+1)
4. For length 2..N+1:
       For i in 0..N+1-length:
           j = i + length
           dp[i][j] = max over k in (i, j) of dp[i][k] + arr[i]*arr[k]*arr[j] + dp[k][j]
5. Answer: dp[0][N+1]

Data Structures Used

2D dp[N+2][N+2].
Padded array arr of size N+2.

Correctness Argument

Claim: dp[i][j] = max coins from bursting all balloons in (i, j) (exclusive), assuming balloons at indices i and j are still present. Proof by induction on length.

Base: length 1 → (i, i+1) has no balloons strictly between → 0.

Inductive step: any optimal bursting order has a last balloon k in (i, j). When k is burst, all other balloons in (i, k) and (k, j) have already been burst, and k’s neighbors are arr[i] and arr[j] (because k is the last to go). The two subintervals (i, k) and (k, j) are independent — neither affects the other since they’re separated by k itself, which is alive until the end. So:

dp[i][k] = max coins from bursting (i, k) (boundaries i, k alive).
dp[k][j] = max coins from bursting (k, j) (boundaries k, j alive).
arr[i] * arr[k] * arr[j] = coins from bursting k last with neighbors i, j.

Sum and maximize over k. The induction works because both subintervals are strictly shorter than (i, j).

Complexity

Stage	Time	Space
Brute force	O(N!)	O(N)
Memoized	O(N³)	O(N²)
Tabulated	O(N³)	O(N²)
Space-optimized	(no further reduction; subproblems span all of `(i, j)`)	O(N²)

At N=500, N³ = 1.25 × 10^8 — close to the edge but passes.

Implementation Requirements

# ---- Stage 1: Brute force ----
def burst_brute(nums):
    arr = [1] + nums + [1]
    def f(active):
        if not active: return 0
        best = 0
        for idx in range(len(active)):
            k = active[idx]
            left  = active[idx-1] if idx > 0 else 0
            right = active[idx+1] if idx+1 < len(active) else len(arr) - 1
            gain = arr[left] * arr[k] * arr[right]
            best = max(best, gain + f(active[:idx] + active[idx+1:]))
        return best
    return f(list(range(1, len(arr) - 1)))

# ---- Stage 2: Memoized (think-backwards reformulation) ----
from functools import lru_cache
def burst_memo(nums):
    arr = [1] + nums + [1]
    @lru_cache(None)
    def f(i, j):
        if j - i < 2: return 0
        return max(
            f(i, k) + arr[i] * arr[k] * arr[j] + f(k, j)
            for k in range(i + 1, j)
        )
    return f(0, len(arr) - 1)

# ---- Stage 3: Tabulated 2D ----
def maxCoins(nums):
    arr = [1] + nums + [1]
    n = len(arr)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):
        for i in range(n - length):
            j = i + length
            best = 0
            for k in range(i + 1, j):
                cand = dp[i][k] + arr[i] * arr[k] * arr[j] + dp[k][j]
                if cand > best: best = cand
            dp[i][j] = best
    return dp[0][n-1]

# ---- Stage 4: No further space optimization (full 2D needed); presented as a tighter inner loop ----
def maxCoins_tight(nums):
    arr = [1] + nums + [1]
    n = len(arr)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):
        for i in range(n - length):
            j = i + length
            ai, aj = arr[i], arr[j]
            best = 0
            for k in range(i + 1, j):
                cand = dp[i][k] + ai * arr[k] * aj + dp[k][j]
                if cand > best: best = cand
            dp[i][j] = best
    return dp[0][n-1]

Tests

[3, 1, 5, 8] → 167.
[1, 5] → 10.
[9] → 9.
[1] → 1.
[] → 0.
[1, 1, 1] → 3.
N=100 random — performance smoke test.
Cross-check brute vs memo on N≤7.

Follow-up Questions

“Find the burst order.” → Track the argmax k in each dp[i][j]; recursively reconstruct.
“Each balloon has a different gain function (not multiplicative).” → Same DP shape, plug in any commutative-on-boundaries function.
“Can we burst at most M balloons?” → Add a 3rd dimension dp[i][j][m].
“Stones Game family (LC 877).” → Interval DP with two players; dp[i][j] = max-score-difference.
“Matrix Chain Multiplication.” → Same shape: dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + cost(i,k,j).

Product Extension

Interval DP underlies optimal binary search tree construction, optimal parenthesization for matrix chains in linear algebra libraries, and pricing problems in algorithmic finance (“when to buy/sell a contract that opens an interval”). The “think backwards / last to act” reframing recurs in algorithmic game theory and contract design.

Language/Runtime Follow-ups

Python: at N=500, the inner triple-loop is 1.25 × 10^8 iterations; Python may TLE. PyPy or rewriting the inner loop as a max(...) generator helps.
Java/Go/C++: no concern at this size.
Memoization in Python: lru_cache(None) is fine; works with (i, j) int tuples.
Iterative version: triple-nested loop is most efficient; avoid generator overhead.

Common Bugs

Trying “first to burst” recurrence and memoizing on (i, j) — incorrect because the subproblems’ boundaries change as outer balloons are burst.
Forgetting to pad with 1 at both ends — out-of-bounds neighbors then need special-casing in every loop iteration.
Iterating by i, j row-major — dp[i][k] for k > j (which we never compute) is never read, but dp[k][j] for k < j is; the row-major order computes dp[i][k] before dp[i][j] only sometimes. Iterate by length.
Off-by-one in range(i + 1, j) — k must be strictly between i and j. Easy to write range(i, j) or range(i + 1, j + 1) and break the recurrence.
Initializing best = -1 — wrong because all values are non-negative and dp[i][j] = 0 for empty intervals is correct.

Debugging Strategy

For [3, 1, 5, 8] (padded to [1, 3, 1, 5, 8, 1]):

Length 2 (no balloons strictly between): all dp = 0.
Length 3: e.g., dp[0][2] = arr[0]*arr[1]*arr[2] = 1*3*1=3. dp[1][3] = 3*1*5 = 15. dp[2][4] = 1*5*8 = 40. dp[3][5] = 5*8*1 = 40.
Length 4: e.g., dp[0][3] = max over k=1,2 of dp[0][k] + 1*arr[k]*5 + dp[k][3] = max(0 + 1*3*5 + 15, 3 + 1*1*5 + 0) = max(30, 8) = 30.
Continue up to dp[0][5] = 167.

Print dp row by row and verify against the trace.

Mastery Criteria

Recognized the contiguity issue with “first to burst” within 90 seconds.
Articulated the “think backwards / last to burst” reformulation in <60 seconds.
Wrote the corrected recurrence on a whiteboard in <2 minutes.
Wrote the tabulated O(N³) solution in <8 minutes from blank screen.
Padded nums with sentinels correctly without prompting.
Iterated by interval length without prompting.
Stated O(N³) time and O(N²) space.
Solved LC 312 unaided in <20 minutes.
Solved Matrix Chain Multiplication in <12 minutes via the same template.

LeetCode Interview — Extreme Coding