Burst Balloons: Interval DP with the Last-Burst Trick

You are given an array of balloons, each with a number painted on it. When you burst balloon i, you collect nums[i-1] * nums[i] * nums[i+1] coins, using the values of the left and right neighbors at the moment of bursting. After bursting, the balloon is gone and its neighbors close up. Burst all the balloons and maximize the total coins collected.

This is 312. Burst Balloons, and it is one of the trickiest interval DP problems on LeetCode. The array is small (up to 500 elements) but the brute-force approach is O(n!) and even clever greedy ideas fall apart. The key is a reframing that turns a tangled dependency problem into a clean recurrence.

Why thinking about the first balloon to burst fails

Your first instinct might be to pick which balloon to burst first in each subproblem. Say you decide to burst balloon k first in the range [i, j]. The coins you get are nums[i-1] * nums[k] * nums[j+1], using the current neighbors of k. But once k is gone, the neighbors of every remaining balloon have changed. Now k-1 and k+1 are adjacent, so their future bursting costs depend on which other balloons have already been removed.

This creates a cascading dependency: the cost of bursting any remaining balloon depends on the entire history of previous bursts. You cannot decompose the problem into independent subproblems, so memoization does not help. Every choice of "first burst" produces a different, incompatible subproblem.

The insight: think about the last balloon to burst

Here is the trick. Instead of asking "which balloon do I burst first?", ask "which balloon do I burst last in this interval?"

If balloon k is the last to be burst in the interval (i, j) (using exclusive boundaries), then when you burst k, all other balloons inside that interval are already gone. The only neighbors of k at the moment of bursting are i and j, the fixed boundaries. This means the coins from bursting k last are exactly nums[i] * nums[k] * nums[j], regardless of what order everything else inside was burst.

And the subproblems split cleanly: everything inside (i, k) was burst before k, with boundaries i and k. Everything inside (k, j) was burst before k, with boundaries k and j. Those two subproblems are completely independent of each other.

Padding and the DP definition

To handle the edge boundaries without special cases, pad the array with 1s at both ends. If your original array is [3, 1, 5, 8], the padded array is [1, 3, 1, 5, 8, 1].

Define dp[i][j] as the maximum coins you can collect by bursting all balloons strictly between index i and index j (exclusive boundaries). The boundaries themselves are never burst.

The recurrence: for each possible last balloon k strictly between i and j,

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

Fill the table by increasing interval length. When you compute dp[i][j] for a given length, all shorter intervals (dp[i][k] and dp[k][j]) are already filled. The answer is dp[0][n-1] where n is the length of the padded array.

Python solution

def maxCoins(nums: list[int]) -> int:
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):
        for left in range(0, n - length):
            right = left + length
            for k in range(left + 1, right):
                dp[left][right] = max(
                    dp[left][right],
                    dp[left][k] + nums[left] * nums[k] * nums[right] + dp[k][right]
                )
    return dp[0][n - 1]

The outer loop iterates over interval lengths from 2 upward (length 2 means one balloon inside, since boundaries are exclusive). For each (left, right) pair, you try every valid k as the last burst. The padded boundaries ensure nums[left] and nums[right] are always valid array accesses, even at the edges.

Step-by-step walkthrough

Complexity analysis

Time: O(n^3). There are O(n^2) intervals, and for each interval you try up to O(n) choices of k.

Space: O(n^2). The DP table stores one value per interval.

For n up to 500 (padded to 502), O(n^3) is about 125 million operations. That is tight but passes within the time limit. The space is manageable at around 250,000 entries.

The building blocks

Interval DP (think about what happens last, not first). The defining move of interval DP is reversing the question. "What happens last in this interval?" produces clean, independent subproblems because the last event sees stable boundaries. "What happens first?" creates dependency on future state and breaks memoization. This exact reversal appears in Matrix Chain Multiplication, Optimal BST, and Zuma Game. Whenever you see a problem where choosing what to do first creates messy dependencies, ask what happens last instead.

Boundary padding trick. Adding sentinel values (usually 0 or 1) at the edges of an array lets you write a single unified recurrence without special-casing the boundaries. For Burst Balloons, padding with 1s means the formula nums[left] * nums[k] * nums[right] always has valid neighbors, even for the leftmost and rightmost real balloons. This technique shows up in many array DP problems where edge elements would otherwise need separate handling.

Edge cases to watch for

• Single balloon: nums = [5]. Padded: [1, 5, 1]. dp[0][2] with k=1 gives 1 * 5 * 1 = 5. Correct.
• All same values: nums = [3, 3, 3]. The order of bursting matters, but the formula handles it. Burst the middle one last for the boundary coins.
• Two balloons: nums = [a, b]. You have two choices: burst a first (coins 1*a*b + 1*b*1) or burst b first (coins 1*a*b + 1*a*1). The DP tries both and picks the best. With [1, 2]: burst 2 first (coins 2 + 1 = 3) vs burst 1 first (coins 2 + 2 = 4). Answer: 4.

From understanding to recall

Reading through this solution and understanding the last-burst insight is the easy part. The hard part is reproducing it under pressure: remembering to pad the array, writing the recurrence correctly with exclusive boundaries, iterating in the right order (by length, not by left index), and returning dp[0][n-1].

Spaced repetition closes that gap. You revisit this problem at increasing intervals, each time writing the DP from scratch. After a few reps, the reframing from "first burst" to "last burst" becomes automatic. You see an interval problem with messy dependencies and your hands already know to flip the question.

The interval DP pattern and the boundary padding trick are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding problems randomly and hoping the patterns stick.

Related posts

• Palindrome Partitioning II - Another interval-style DP that fills a 2D table bottom-up
• Different Ways to Add Parentheses - Divide-and-conquer over every split point, the recursive cousin of interval DP
• Unique Binary Search Trees - Catalan number DP that also iterates over all possible root choices for an interval