Burst Balloons: Interval DP Problem

Key Insights

The critical mental shift is thinking about which balloon to burst last in a range, not first—this creates independent subproblems that don’t affect each other
Interval DP problems require iterating by interval length (small to large), not by starting index, because larger intervals depend on smaller ones
Adding virtual balloons with value 1 at boundaries eliminates edge case handling and simplifies the recurrence relation

Problem Introduction

LeetCode 312 - Burst Balloons presents a deceptively simple premise: you have n balloons with values, and bursting balloon i gives you nums[i-1] * nums[i] * nums[i+1] coins. After bursting, adjacent balloons become neighbors. Find the maximum coins you can collect by bursting all balloons.

The constraints are modest (n <= 300), but the naive approach is catastrophic. With n balloons, you have n! possible bursting orders—that’s approximately 10^614 operations for n=300. Even with memoization on the remaining balloon set, you’re looking at 2^n subsets, which is still intractable.

This problem belongs to the interval dynamic programming family, a pattern that appears frequently in competitive programming and interviews. Mastering it unlocks solutions to matrix chain multiplication, optimal binary search trees, and stone merging problems.

Why Greedy Doesn’t Work

Your first instinct might be greedy: always burst the balloon that gives maximum (or minimum) coins. Let’s see why this fails.

def burst_balloons_greedy(nums: list[int]) -> int:
    """Greedy approach: always burst the balloon giving max coins."""
    if not nums:
        return 0
    
    balloons = list(nums)
    total = 0
    
    while balloons:
        max_coins = 0
        max_idx = 0
        
        for i in range(len(balloons)):
            left = balloons[i - 1] if i > 0 else 1
            right = balloons[i + 1] if i < len(balloons) - 1 else 1
            coins = left * balloons[i] * right
            
            if coins > max_coins:
                max_coins = coins
                max_idx = i
        
        total += max_coins
        balloons.pop(max_idx)
    
    return total

# Counterexample
nums = [3, 1, 5, 8]
print(f"Greedy result: {burst_balloons_greedy(nums)}")  # Output: 134
print(f"Optimal result: 167")  # The actual maximum

For [3, 1, 5, 8], greedy produces 134, but the optimal answer is 167. The greedy approach fails because bursting decisions have cascading effects—removing a balloon changes the neighbors of adjacent balloons, affecting all future calculations. There’s no local decision rule that guarantees global optimality.

The same logic defeats “burst minimum first” strategies. The interdependence between decisions means we need to consider all possible orderings systematically.

Key Insight: Think in Reverse

Here’s the mental shift that unlocks this problem: instead of asking “which balloon should I burst first?”, ask “which balloon should I burst last in this range?”

Why does this matter? Consider a range of balloons from index i to j. If we decide balloon k is burst last in this range:

When we burst k, all other balloons in [i, j] are already gone
The coins we get from k are nums[i-1] * nums[k] * nums[j+1] (the boundaries, not neighbors)
The left subproblem [i, k-1] and right subproblem [k+1, j] are now independent

This independence is crucial. When we burst balloons in [i, k-1], balloon k is still there as the right boundary. Similarly, k serves as the left boundary for [k+1, j]. The subproblems don’t interfere with each other.

Thinking forward (which to burst first) creates dependent subproblems—the remaining balloons form a single connected sequence. Thinking backward (which to burst last) creates independent subproblems that we can solve separately and combine.

Interval DP Formulation

Let’s formalize this insight. Define dp[i][j] as the maximum coins obtainable by bursting all balloons in the range (i, j) exclusive—meaning balloons at indices i+1, i+2, ..., j-1.

We pad the original array with 1s at both ends to handle boundary conditions elegantly:

padded = [1] + nums + [1]
# For nums = [3, 1, 5, 8]
# padded = [1, 3, 1, 5, 8, 1]
# indices:  0  1  2  3  4  5

The recurrence relation:

dp[i][j] = max(
    dp[i][k] + padded[i] * padded[k] * padded[j] + dp[k][j]
) for all k in (i+1, i+2, ..., j-1)

Breaking this down:

dp[i][k]: max coins from bursting all balloons between i and k
padded[i] * padded[k] * padded[j]: coins from bursting balloon k last (when only boundaries remain)
dp[k][j]: max coins from bursting all balloons between k and j

Base case: dp[i][i+1] = 0 (no balloons between adjacent indices).

The key constraint on iteration order: we must solve smaller intervals before larger ones, since dp[i][j] depends on dp[i][k] and dp[k][j] where both intervals are strictly smaller than [i, j].

Implementation

Here’s the complete bottom-up solution:

def max_coins(nums: list[int]) -> int:
    """
    Burst Balloons using Interval DP.
    Time: O(n³), Space: O(n²)
    """
    if not nums:
        return 0
    
    # Pad with virtual balloons of value 1
    padded = [1] + nums + [1]
    n = len(padded)
    
    # dp[i][j] = max coins from bursting all balloons in range (i, j) exclusive
    dp = [[0] * n for _ in range(n)]
    
    # Iterate by interval length (gap between i and j)
    # Length 2 means adjacent indices -> no balloons between -> base case (0)
    # Start from length 3 (one balloon between i and j)
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            # Try each balloon k as the last to burst in range (i, j)
            for k in range(i + 1, j):
                # Coins from left subproblem + bursting k + right subproblem
                coins = (dp[i][k] + 
                        padded[i] * padded[k] * padded[j] + 
                        dp[k][j])
                dp[i][j] = max(dp[i][j], coins)
    
    # Answer: max coins from bursting all balloons between index 0 and n-1
    return dp[0][n - 1]

public class BurstBalloons {
    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        // Pad with virtual balloons
        int n = nums.length + 2;
        int[] padded = new int[n];
        padded[0] = padded[n - 1] = 1;
        for (int i = 0; i < nums.length; i++) {
            padded[i + 1] = nums[i];
        }
        
        int[][] dp = new int[n][n];
        
        // Iterate by interval length
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                
                for (int k = i + 1; k < j; k++) {
                    int coins = dp[i][k] 
                              + padded[i] * padded[k] * padded[j] 
                              + dp[k][j];
                    dp[i][j] = Math.max(dp[i][j], coins);
                }
            }
        }
        
        return dp[0][n - 1];
    }
}

The iteration order is critical. We process intervals from smallest (length 3) to largest (full array). Within each length, we iterate through all possible starting positions. This guarantees that when we compute dp[i][j], all smaller intervals dp[i][k] and dp[k][j] are already solved.

Complexity Analysis & Optimization

Time Complexity: O(n³)

O(n) interval lengths
O(n) starting positions per length
O(n) choices for the last balloon k

Space Complexity: O(n²)

The DP table has n² entries

This cubic time complexity is inherent to interval DP problems where we must consider all possible split points. For n=300, we’re looking at roughly 27 million operations—well within acceptable limits.

Space optimization is theoretically possible using the observation that computing intervals of length L only requires intervals of length less than L. However, the access pattern isn’t strictly sequential, making optimization complex without significant code clarity loss. For interview and competitive programming contexts, O(n²) space is acceptable.

Burst Balloons exemplifies a broader pattern. Here’s a template for interval DP problems:

def interval_dp_template(arr: list) -> int:
    """
    Generic interval DP template.
    Customize cost() and combine() for specific problems.
    """
    n = len(arr)
    # Often need padding: arr = [boundary] + arr + [boundary]
    
    dp = [[0] * n for _ in range(n)]
    
    # Base cases: intervals of length 1 or 2
    # for i in range(n): dp[i][i] = base_value
    
    # Iterate by interval length
    for length in range(2, n + 1):  # or 3 if using exclusive ranges
        for i in range(n - length + 1):
            j = i + length - 1
            
            dp[i][j] = float('inf')  # or 0 for maximization
            
            # Try all split points
            for k in range(i, j):  # or (i+1, j) for exclusive
                candidate = dp[i][k] + dp[k+1][j] + cost(i, j, k)
                dp[i][j] = min(dp[i][j], candidate)  # or max
    
    return dp[0][n - 1]

Related problems sharing this pattern:

Matrix Chain Multiplication: Minimize scalar multiplications to compute matrix product. Split point k determines which multiplication happens last.
Minimum Cost to Merge Stones (LeetCode 1000): Merge consecutive piles with cost equal to sum. Harder variant with constraint on merge size.
Optimal Binary Search Tree: Minimize expected search cost given access frequencies. Split point becomes root of subtree.
Palindrome Partitioning II: Minimum cuts to partition string into palindromes. Combines interval DP with palindrome checking.

The unifying theme: problems where you must process a sequence, the cost depends on what remains, and choosing a “split point” or “last operation” creates independent subproblems. When you see these characteristics, reach for interval DP.