What Is Interval DP? The Subarray State That Wins Hard Problems

Coin change. House robber. LIS. You've solved them. You've written the recurrences from memory. You feel, finally, comfortable with DP.

Then you open Burst Balloons and every angle you try melts. Backtracking explodes. Greedy doesn't even make contact with the problem. You stare at the constraints. You read the problem four times. You try "burst the smallest balloon first" and get wrong answers. You try "burst the edges" and get wrong answers.

Eventually an editorial hint says "define dp[i][j] as the maximum coins in range (i, j)" and something shifts.

That two-index state is interval DP. Here's how it works, where it breaks, and how to recognize it before you're already 25 minutes deep into the wrong solution.

The State Nobody Teaches You

Most DP uses one index. dp[i] means "the best answer for the first i elements." That handles coin change, house robber, and longest increasing subsequence.

Interval DP uses two. dp[i][j] means "the best answer for the subarray from index i to index j." The question shifts from "what's optimal up to position i?" to "what's optimal over this specific window?"

Reframing the problem over a range instead of a prefix unlocks an entire class of hard problems. Things that looked like they needed exponential backtracking turn out to have clean polynomial recurrences. The catch is that almost no intro DP tutorial covers this. You graduate from one-index DP, feel confident, and then Burst Balloons introduces itself.

The setup is always a linear sequence: a string, an array, or a chain of matrices. For each contiguous subrange, you want some optimal value. A length-1 range is trivial. Larger ranges are built from smaller ones by trying every possible split point in the middle. If you've seen overlapping subproblems before, this is the same idea applied across a 2D table instead of a 1D array.

Fill By Length, Not By Row

Here is the skeleton. The outer loop is where most implementations go wrong.

n = len(arr)
dp = [[0] * n for _ in range(n)]

for i in range(n):
    dp[i][i] = base_value(i)

for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
        dp[i][j] = float('inf')
        for k in range(i, j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + cost(i, k, j))

return dp[0][n - 1]

The outer loop iterates by interval length. Not optional.

dp[i][j] depends on dp[i][k] and dp[k+1][j], both shorter intervals. If you fill row by row, you will read values that have not been written yet. Fill by length instead: all length-2 intervals before all length-3 intervals, and so on. Draw the dependency arrows on a 4-element example and you will see immediately why row order fails. This is the same dependency reasoning behind standard bottom-up DP, applied diagonally across a 2D table.

Row-by-row feels natural because that is how every other 2D loop you have written works. It is the wrong instinct here.

Spongebob meme: computers do exactly what you tell them, not what you want

Your table fills row-by-row, cheerfully reading cells that haven't been computed yet.

A Simple Case: Longest Palindromic Subsequence

LeetCode 516 asks for the length of the longest subsequence of a string that reads the same forward and backward. It is a gentle on-ramp before the chaos of Burst Balloons.

Define dp[i][j] as the length of the longest palindromic subsequence in s[i..j].

Base case: dp[i][i] = 1. A single character is always a palindrome.

Transition: compare the endpoints.

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = 1

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                inner = dp[i + 1][j - 1] if length > 2 else 0
                dp[i][j] = inner + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

    return dp[0][n - 1]

No split-point loop. The recurrence only asks: do the outer characters match? If yes, wrap them around the inner palindrome and add 2. If no, drop one endpoint and take the better result.

This is interval DP at its simplest. No clever inversion, no boundary tricks, just a two-index state and a clean recurrence. O(n²) time and O(n²) space.

The Hard One: Burst Balloons

LeetCode 312 is the problem that properly introduces most engineers to interval DP.

You have n balloons with numeric values. Bursting balloon i when its neighbors are l and r earns you nums[l] * nums[i] * nums[r] coins. Find the maximum total coins from bursting all balloons in any order.

The obvious approach recurses on "which balloon do I burst first?" It fails immediately. Bursting balloon i removes it and makes its former neighbors adjacent. Left subproblem and right subproblem are no longer independent, because the boundary between them just changed. Every split point creates a mess.

The fix is to think about the last balloon you burst in each range, not the first.

When balloon k is the last one remaining inside a range bounded by positions left and right, you know exactly what its neighbors will be: nums[left] and nums[right]. Nothing between them remains. The coins from that final burst are nums[left] * nums[k] * nums[right], no unknown neighbors in the calculation. The left portion (left, k) and the right portion (k, right) were already solved as independent subproblems.

This is the inversion. Instead of "what do I do first?", ask "what is still standing at the end?" It sounds backwards. It is backwards. It also works.

Add virtual boundary balloons with value 1 at both ends. Define dp[left][right] as the maximum coins from bursting every balloon strictly inside (left, right).

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):
                coins = nums[left] * nums[k] * nums[right]
                dp[left][right] = max(
                    dp[left][right],
                    dp[left][k] + dp[k][right] + coins
                )

    return dp[0][n - 1]

The "last instead of first" inversion is what makes the subproblems independent. Before you see it, the problem is a wall. After, it feels obvious. This inversion appears in a handful of hard interval DP problems, and Burst Balloons is the best place to internalize it.

Why O(n³)?

Count the work directly. There are O(n²) valid intervals. For each, you try O(n) split points. Each split costs O(1). Total: O(n³).

Space is O(n²) for the table. Unlike linear DP, rolling arrays do not apply here. Interval DP needs every smaller interval in memory when computing a larger one.

For n around 300 to 500, O(n³) is fast enough. That constraint range is itself a recognition signal. When a problem says n ≤ 500 and the naive approach is exponential, O(n³) is exactly the target complexity to aim for.

How to Spot an Interval DP Problem

You rarely need all the signals. Two or three are enough.

The subproblem is a contiguous range, not a prefix. If the optimal answer on a window depends only on what's inside it, not what came before, two indices are probably needed.

The final answer sits at dp[0][n-1]. When you sketch the recursion and realize you want "the whole string" or "the whole array," that is a flag.

Forward reasoning creates tangled dependencies. When "which element do I process first?" makes subproblems non-independent, try "which element is last?" That flip is the key insight behind Burst Balloons and Strange Printer.

The constraint is n ≤ 500 or so. O(n³) for n = 500 is 125 million operations, on the edge but typically acceptable in interviews.

Problem keywords. "Palindrome," "merge adjacent segments," "optimal parenthesization," "remove for maximum score," "two players play optimally on a sequence." Matrix chain multiplication on Wikipedia is the earliest formalization of the pattern and worth reading even if it rarely appears verbatim in interviews.

Where Implementations Break

Filling the table row by row. Every 2D DP instinct you have says for i in range(n): for j in range(n). Interval DP violates this. Fix: fill by interval length. Draw the dependency arrows on n = 4 and you will see why immediately.

Thinking forward in Burst Balloons-style problems. "Which balloon do I burst first?" creates non-independent subproblems. "Which balloon is last?" isolates them. When a problem has this flavor and your recurrence won't simplify, try the inversion.

Off-by-one on boundaries. In Burst Balloons the intervals are exclusive: dp[left][right] covers balloons strictly between left and right. The boundary balloons are never burst. Getting this wrong produces wrong answers on small inputs that are deeply annoying to track down.

Skipping the length-2 guard. When length == 2, the inner interval dp[i+1][j-1] degenerates to dp[i+1][i], which is an invalid cell. Guard it explicitly, as the palindromic subsequence code does with if length > 2.

Guy throwing salt meme: when you can't find the bug

Interval DP after an off-by-one on the exclusive boundary. The answer is always wrong by exactly enough to be confusing.

Start With These Five Problems

Work through them roughly in order.

Longest Palindromic Subsequence (516), the clean entry point. No split-point loop, just endpoint comparison.
Minimum Cost to Cut a Stick (1547), classic merge-cost variant. The cost at each split is the current segment length.
Strange Printer (664), if the endpoints match, save a turn. Good for building recurrence intuition.
Burst Balloons (312), the definitive interval DP problem. Do not skip it.
Minimum Score Triangulation of a Polygon (1039), geometric framing, same split-point recurrence underneath.

The dynamic programming framework applies here too: define the state precisely, write the recurrence on paper, verify base cases, then implement. The only interval-DP-specific addition is checking that fill order respects dependencies.

Four Things to Memorize

dp[i][j] stores the optimal answer for the range i to j. That two-index state is the defining feature.
Fill by increasing interval length. Row-by-row order violates dependencies.
When forward reasoning breaks, flip to "which element is last?" The subproblems usually become independent.
Recognition signals: contiguous range matters, final answer at dp[0][n-1], naive recursion blows up on dependency cycles, n ≤ 500.

If you want to practice explaining this recurrence under interview conditions, including follow-up questions about traversal order and why the "last operation" trick works, SpaceComplexity runs voice-based mock interviews with rubric scoring. Deriving the recurrence silently is one skill. Narrating it while a timer runs is another.