Chapter 16: Interval DP - Burst Balloons

We've covered a wide range of DP patterns, from simple 1D arrays to complex state machines. Now, we'll introduce another powerful paradigm: Interval DP. In these problems, the state is defined not by a single index, but by a continuous sub-array or interval, typically denoted as dp[i][j]. The goal is to find an optimal value for the entire array by first solving for all smaller sub-arrays.

A quintessential example is LeetCode's "Burst Balloons" (Problem #312). This problem is known for its clever solution, which hinges on thinking about the problem in reverse.

The Problem:

You are given n balloons, indexed from 0 to n - 1. Each balloon has a number painted on it represented by the array nums. You are asked to burst all the balloons.

If you burst the i-th balloon, you will get nums[left] * nums[i] * nums[right] coins, where left and right are the adjacent indices to i. After the burst, the left and right balloons become adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note: You may imagine nums[-1] = nums[n] = 1. These are not real balloons so they cannot be burst.

For example:

• nums = [3, 1, 5, 8]

• Output: 167

• Explanation:

  • [3, 1, 5, 8] --> [3, 5, 8] (burst 1, coins = 315 = 15)

  • [3, 5, 8] --> [3, 8] (burst 5, coins = 358 = 120)

  • [3, 8] --> [8] (burst 3, coins = 138 = 24)

  • [8] --> [] (burst 8, coins = 181 = 8)

  • Total coins = 15 + 120 + 24 + 8 = 167

The Challenge of a Direct Approach

A naive recursive approach might be: "which balloon should I burst next?". If we try to solve solve(current_balloons), we find that bursting one balloon affects the adjacency of its neighbors, which makes the resulting subproblems dependent on each other. This is very difficult to memoize.

The Key Insight: Thinking in Reverse

The trick is to change the question from "Which balloon do I burst first?" to "Which balloon in this interval (i, j) do I burst last?".

Let's say we decide to burst balloon k (where i < k < j) last within the interval of balloons originally between i and j. When we burst k, all other balloons between i and j have already been burst. This means its neighbors are the boundary balloons at i and j. The coins we get from this last burst are nums[i] * nums[k] * nums[j].

Crucially, because k is the last one burst in this interval, its bursting doesn't affect the subproblems to its left (balloons between i and k) and to its right (balloons between k and j). They are completely independent!

This gives us a clean recurrence: max_coins(i, j) = max( max_coins(i, k) + (nums[i] * nums[k] * nums[j]) + max_coins(k, j) ) for all k from i+1 to j-1.

Approach 1: The Recursive Solution (with the right insight)

First, we'll pad the nums array with 1s at both ends to handle the boundary conditions easily. Let solve(i, j) be the max coins from bursting balloons in the open interval (i, j).

from typing import List

def maxCoins_recursive(nums: List[int]) -> int:
    # Add boundary 1s
    nums = [1] + nums + [1]
    n = len(nums)

    def solve(i, j):
        # Base case: no balloons to burst in the interval
        if i + 1 == j:
            return 0

        max_val = 0
        # k is the last balloon to be burst in the interval (i, j)
        for k in range(i + 1, j):
            current_coins = solve(i, k) + (nums[i] * nums[k] * nums[j]) + solve(k, j)
            max_val = max(max_val, current_coins)

        return max_val

    return solve(0, n - 1)

# Trying it out
# print(maxCoins_recursive([3, 1, 5, 8])) # 167
# This is correct but will be very slow.

Approach 2: Memoization with a Decorator (Top-Down DP)

The state is (i, j), which is a perfect candidate for caching.

import functools
from typing import List

class Solution:
    def maxCoins_memoized(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]
        n = len(nums)

        @functools.lru_cache(maxsize=None)
        def solve(i, j):
            if i + 1 >= j:
                return 0

            max_val = 0
            for k in range(i + 1, j):
                current_coins = solve(i, k) + (nums[i] * nums[k] * nums[j]) + solve(k, j)
                max_val = max(max_val, current_coins)

            return max_val

        return solve(0, n - 1)

# Trying it out
# solver = Solution()
# print(solver.maxCoins_memoized([3,1,5,8])) # 167

With memoization, the time complexity is roughly O(n^3) because there are O(n^2) states (i, j), and each state involves an O(n) loop.

Approach 3: Iteration (Bottom-Up DP)

We can build the solution iteratively using a 2D dp array, where dp[i][j] stores the solution for the interval (i, j). We must solve for smaller intervals first.

1. Pad nums with 1s.

2. Create an n x n DP table.

3. Iterate over the length of the interval, l, from 2 to n.

4. For each length, iterate through all possible start indices i. The end index j will be i + l.

5. For each interval (i, j), iterate through all possible "last balloons" k from i+1 to j-1 and compute dp[i][j] using the recurrence.

def maxCoins_iterative(nums: List[int]) -> int:
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    # l is the length of the interval
    for l in range(2, n):
        # i is the start of the interval
        for i in range(n - l):
            j = i + l
            # k is the last balloon to burst in (i, j)
            for k in range(i + 1, j):
                dp[i][j] = max(dp[i][j], dp[i][k] + (nums[i] * nums[k] * nums[j]) + dp[k][j])

    return dp[0][n-1]

# Trying it out
# print(maxCoins_iterative([3, 1, 5, 8])) # 167

Conclusion

"Burst Balloons" is a pivotal problem in dynamic programming. It teaches the invaluable lesson that sometimes, the most intuitive, forward-looking approach leads to tangled subproblems. By reframing the question—focusing on the last action in an interval rather than the first—we can unlock a clean, independent substructure that is perfectly suited for DP. This "think in reverse" strategy is the key to mastering interval-based dynamic programming.