L42 · DP X — Interval DP

Series: LeetCode — From Basics to Interview-Ready · Session 42 / 65 · Phase 2 · Dynamic programming

Why this session exists

Interval DP is genuinely hard, and I want to say that plainly rather than pretend the pattern makes it easy. The skeleton is three nested loops and about eight lines. Recognising that a problem needs it, and finding the right thing to put at the split point, is the difficult part and no template rescues you from it.

The trick in Burst Balloons is thinking about the last balloon in a range rather than the first. That inversion is the whole session. If you ask "which balloon do I burst first", the two remaining pieces are not independent — bursting a balloon changes who its neighbours are, so the left piece's answer depends on what happened in the right piece. The subproblems overlap in a way that destroys the recurrence.

If instead you ask "which balloon is the last one standing in this range", everything works. The last balloon's neighbours at the moment it bursts are, by definition, the two balloons just outside the range — because everything inside the range is already gone. That fact is fixed and known. So the left sub-range and the right sub-range become genuinely independent, and you can add their answers.

That reversal — from first to last — is not a trick specific to balloons. It is the general move for interval problems where operations interact. Matrix chain multiplication asks which multiplication you do last. Optimal binary search tree asks which key is the root. Same shape, same reason.

Blank-file warm-up

Five minutes, empty file, no notes. Write the interval DP skeleton:

1. The outer loop over interval length, not over i.
2. The derivation of j from i and the length.
3. The inner loop for k in range(i, j) combining dp[i][k] and dp[k][j].

You are not solving a problem here. You are proving you can produce the loop structure cold, because in an interview the structure is what you write while you are still thinking about the recurrence.

Pattern anatomy

The shape that summons this pattern: a contiguous range that gets consumed by operations, where the cost of an operation depends on what is adjacent to it at the time. That last clause is the discriminator. If costs were independent of order, you would sort or greedily pick and never need a table.

The invariant: dp[i][j] is the best achievable value for the range strictly between boundaries i and j — or inclusive of both, depending on the problem, and being sloppy about which is the fastest way to lose an hour. Pick a convention, write it in a comment, and hold it.

Dependencies flow from shorter ranges to longer ones. dp[i][j] reads dp[i][k] and dp[k][j], both of which are strictly shorter than [i, j]. That is why the outer loop must be over length: any other order reads unfilled cells.

def interval_dp(n: int) -> int:
    # convention: dp[i][j] = best value for the OPEN interval (i, j)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
 
    for length in range(2, n + 1):          # length of the span i..j
        for i in range(0, n + 1 - length):
            j = i + length
            best = float("-inf")
            for k in range(i + 1, j):       # k is the LAST element handled
                value = dp[i][k] + dp[k][j] + cost(i, k, j)
                best = max(best, value)
            dp[i][j] = best
    return dp[0][n]

Three loops: length, left endpoint, split point. O(n³) time, O(n²) space. The cost(i, k, j) term is the entire problem-specific content, and it is where you spend your thinking.

For Burst Balloons the cost is nums[i] * nums[k] * nums[j] — the value of bursting balloon k when its surviving neighbours are exactly the boundaries i and j. That expression is only correct because of the last-not-first framing.

The cue

You are looking at interval DP when the statement contains these tells:

1. n around 100 to 500. This is the loudest tell in the whole session. O(n³) at n = 500 is 125 million operations — borderline but plausible in a fast language, comfortable at n = 100. When you see a suspiciously small n on an array problem, cubic is being invited.
2. Operations remove or merge adjacent elements, and removal changes adjacency. Bursting, cutting, merging stones, multiplying matrices. If removing an element makes two other elements become neighbours, the order matters and greedy will not save you.
3. "Minimum cost to reduce to one" or "maximum score to remove everything". Both phrasings describe reducing a range by repeated local operations.
4. The cost of one operation references its current neighbours rather than fixed positions. nums[i-1] * nums[i] * nums[i+1] where the indices shift as things are removed.
5. A greedy that feels right but you can break with a small counter-example. Burst Balloons has an obvious greedy — burst the smallest first, or the largest first — and both are wrong on three-element inputs. If your first instinct is greedy and you can break it in under a minute, the answer is usually interval DP.

Tell 1 plus tell 2 together is close to conclusive. Small n and order-dependent adjacency means build the triangle.

Guided solve

Burst Balloons — you have n balloons with values nums[i]. Bursting balloon i earns nums[i-1] * nums[i] * nums[i+1], where out-of-range neighbours count as 1. After bursting, the neighbours become adjacent. Maximise total coins.

Start with the naive framing so you can watch it fail, because articulating the failure is what earns the points.

Naive: let dp[i][j] be the best score for range [i, j], and choose which balloon to burst first. Then you would want dp[i][k-1] + dp[k+1][j] + something. But what is the something? When you burst k first, its neighbours are nums[k-1] and nums[k+1], both still present. Fine. But now the left sub-range [i, k-1] will eventually burst its rightmost balloon, and at that moment its right neighbour is whatever survives from the right sub-range. The two halves are coupled. The recurrence is not well-defined. Stop here and say so — this is the moment the interviewer is actually evaluating.

Now the reversal. Define dp[i][j] as the best score for bursting every balloon strictly between i and j, where i and j themselves are never burst — they are the surviving boundary. Choose k to be the last balloon burst in that open range.

Because k is last, everything strictly between i and k is already gone, and everything strictly between k and j is already gone. So at the moment k bursts, its neighbours are exactly i and j. Its value is nums[i] * nums[k] * nums[j] — fully determined, no coupling.

And the two sub-ranges (i, k) and (k, j) are now independent: each is bounded by balloons that survive throughout that sub-problem, so nothing inside one affects anything inside the other.

def maxCoins(nums):
    vals = [1] + nums + [1]                    # sentinels
    n = len(vals)
    dp = [[0] * n for _ in range(n)]
 
    for length in range(2, n):                 # span from i to j inclusive
        for i in range(0, n - length):
            j = i + length
            for k in range(i + 1, j):          # k burst LAST in the open range
                dp[i][j] = max(
                    dp[i][j],
                    dp[i][k] + dp[k][j] + vals[i] * vals[k] * vals[j],
                )
    return dp[0][n - 1]

Trace nums = [3, 1, 5] briefly. With sentinels, vals = [1, 3, 1, 5, 1]. Length-2 spans are empty inside, so they stay 0. For the span i=0, j=2 the only k is 1, giving 1*3*1 = 3. For i=1, j=3, k=2 gives 3*1*5 = 15. Building up, the full range i=0, j=4 tries k = 1, 2, 3 and the maximum comes out at 35, from bursting 1 first, then 3, then 5 — equivalently, 5 last. The bottom-right corner is the answer.

Solo timed

Fifteen minutes each, timer running, no editorial until it fires.

• Minimum Cost to Cut a Stick — you are given cut positions on a stick. Cutting a piece costs its current length. Same skeleton, but sort the cuts and pad with the two stick endpoints as sentinels first. The cost term is positions[j] - positions[i], independent of k — think about why that is.
• Matrix Chain style / Minimum Score Triangulation — pick any matrix-chain-shaped problem. The cost term is a product of three dimensions and the split point is the last multiplication performed.

If both land early, try Stone Game VII or Remove Boxes — the latter needs a third state dimension and is a real step up, which makes it a good honest test of whether you understood the framing or just memorised the loops.

Common failure modes

Iterating i in the outer loop. The number-one structural bug. dp[i][j] needs shorter spans, and looping i outward-in or row-major reads zeros from unfilled cells. The answer comes out too small and nothing crashes. Always iterate length first.

Mixing open and closed interval conventions. Defining dp[i][j] as "burst everything strictly between" and then writing for k in range(i, j+1) mixes the two. Decide once, write it in a comment above the table, and make every loop bound obey it.

Forgetting the sentinels, then patching with conditionals. You end up with left = nums[i-1] if i > 0 else 1 inside the innermost loop, which works but is four extra branch points in the hottest code path. Pad the array instead.

Choosing the first operation instead of the last. This is the conceptual failure, not a coding one. The symptom is that you cannot write a correct cost term — you keep needing to know what happened in the other half. If you find yourself stuck there, that is the signal to invert.

Cubic blowup on large n. If n is 10^4, interval DP is not the intended solution no matter how well it fits the story. Re-read the constraints before committing to three nested loops.

Complexity

Time: O(n³). There are O(n²) intervals, each trying O(n) split points with constant work per split. At n = 500 that is 125 million inner iterations, which is too slow for Python but fine for C++ — check the constraints and the expected language before committing.

Space: O(n²) for the table. There is no rolling-array reduction here, because dp[i][j] reads cells scattered across the whole triangle rather than a fixed offset back. That is a genuine structural difference from the L40 grid, and worth noticing: you cannot always optimise space away.

Only the upper triangle i < j is ever used, so a triangular representation halves the memory if you need it. Rarely worth the index arithmetic.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Burst Balloons will most likely enter at failed or hint the first time, and that is normal. This is one of the few problems where the honest expectation is that you will not derive it cold on first exposure. Log it truthfully and let the ladder do its job.