Burst Balloons LeetCode 312 — Interval DP

LeetCode 312 Burst Balloons gives you an array of balloons nums where each balloon has a value. When you burst balloon i, you earn nums[i-1] * nums[i] * nums[i+1] coins — the product of the balloon and its current left and right neighbors. Balloons that are burst no longer exist, so neighbors shift together. Your goal is to maximize total coins earned by choosing the optimal bursting order.

For example, with nums = [3, 1, 5, 8], the optimal strategy earns 167 coins. The problem pads the array with imaginary boundary balloons of value 1 at both ends, so nums becomes [1, 3, 1, 5, 8, 1]. This simplification means you never have to worry about out-of-bounds neighbors.

At first glance this looks like a greedy problem — maybe always burst the smallest balloon first. But that intuition breaks down because bursting one balloon changes the neighbors of surrounding balloons, creating complex dependencies. With n up to 500, an O(n^3) solution is needed.

A natural greedy heuristic is to always burst the balloon with the smallest value. The idea is that low-value balloons contribute fewer coins and should be "sacrificed" while neighbors are still small. But this fails on even simple examples — the optimal order is highly non-local and depends on which balloons remain at every step.

Another greedy idea: burst the largest balloon first to maximize each individual gain. This also fails because each burst permanently alters the neighbor structure. Bursting a large balloon early might collapse two high-value neighbors together, setting up a bigger multiplier for a later burst.

The fundamental problem is that forward simulation is irreversible. Once you decide to burst balloon i first, its removal creates a new adjacency that constrains all future decisions. There are n! possible bursting orders, and no greedy rule correctly identifies the optimal one. This forces us toward dynamic programming.

The breakthrough insight that makes this problem tractable is to think in reverse: instead of asking "which balloon do I burst first?", ask "which balloon do I burst last in a given interval?" This single reframing transforms an intractable problem into a clean interval DP.

Consider any subarray from index left to right (exclusive, using the padded array). If balloon k is the last one burst in that interval, then at the moment k is burst, all other balloons in (left, right) are already gone. This means k's neighbors are guaranteed to be the boundary balloons at left and right — not any balloon inside the interval. The coins earned are nums[left] * nums[k] * nums[right].

This is powerful because it decouples the subproblems. The left subinterval (left, k) and the right subinterval (k, right) are now completely independent — bursting anything in (left, k) never affects what happens in (k, right) because k is still present as a boundary throughout. We can solve each sub-interval independently and sum the results.

Define dp[left][right] as the maximum coins obtainable by bursting all balloons in the open interval (left, right), where left and right are boundary indices that remain un-burst. The final answer is dp[0][n+1].

The recurrence is: dp[left][right] = max over all k in (left, right) of (nums[left] * nums[k] * nums[right] + dp[left][k] + dp[k][right]). Here k is the last balloon burst in the interval. When k is burst last, its neighbors are exactly the boundaries left and right.

The time complexity is O(n^3): there are O(n^2) intervals (left, right) and for each we try O(n) choices of k. Space is O(n^2) for the DP table. This is exactly the same structure as the classic Matrix Chain Multiplication problem, which is a useful mental model for understanding why the "last operation" framing works.

To fill the DP table bottom-up, iterate over interval lengths from 2 upward (length 2 means no balloons inside, so dp = 0). For each length, iterate over all valid left endpoints and compute the corresponding right endpoint. Then try all k values inside and take the maximum.

The order of iteration is critical: you must compute smaller intervals before larger ones, because dp[left][right] depends on dp[left][k] and dp[k][right], both of which are shorter intervals. Length-based iteration guarantees this dependency order.

Alternatively, you can use top-down memoization with a recursive function. Both approaches have the same time and space complexity; top-down is often easier to write correctly on first attempt because the recursion naturally handles the dependency order.

In Python, pad the array: nums = [1] + nums + [1]. Initialize dp as an (n+2) x (n+2) grid of zeros. Iterate length from 2 to n+1 inclusive. For each length, iterate left from 0 to n+2-length. Set right = left + length. For each k in range(left+1, right), update dp[left][right] = max(dp[left][right], nums[left]*nums[k]*nums[right] + dp[left][k] + dp[k][right]). Return dp[0][n+1].

In Java, the approach is identical: pad nums into a new int[] array, allocate a 2D int[][] dp table, and use three nested loops (length, left, k). The inner update is dp[left][right] = Math.max(dp[left][right], nums[left]*nums[k]*nums[right] + dp[left][k] + dp[k][right]).

For the memoized top-down version in Python, define dfs(left, right) that returns 0 if right - left < 2. Otherwise iterate k and recurse on both halves. Use @lru_cache(None) for automatic memoization. Both implementations beat ~95% of submissions on LeetCode.

Burst Balloons is the canonical example of interval DP. The same "last operation in an interval" framing appears in Matrix Chain Multiplication (minimize cost of multiplying a chain of matrices), Strange Printer (LeetCode 664), Remove Boxes (LeetCode 546), and Minimum Cost to Merge Stones (LeetCode 1000).

The key signature of interval DP problems is: you have a sequence, you perform operations that affect a contiguous subarray, and the order of operations matters. When you see this signature, try defining dp[left][right] and think about what the last operation in that range looks like.

Connecting Burst Balloons to Matrix Chain Multiplication is especially instructive. In MCM, the last multiplication splits the chain into two independent sub-chains. In Burst Balloons, the last burst splits the interval into two independent sub-intervals. The mathematical structure is identical — this is why both have O(n^3) solutions.