L42 · DP X — Interval DP

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

Watch first

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.

Memory hook — "LAST, not first; LENGTH, not index"

Two capitalised words carry the whole session, and each fixes one of the two things that go wrong.

LAST, not first. When the range is consumed by operations whose cost depends on neighbours, splitting on the first operation couples the halves — the left half's final neighbour is whatever survives on the right. Splitting on the last operation decouples them, because by definition everything else inside the range is already gone, so the last operation's neighbours are exactly the two fixed boundaries. The peg: "the last one standing sees only the walls."

LENGTH, not index. dp[i][j] depends on strictly shorter intervals dp[i][k] and dp[k][j]. A row-major loop over i reads intervals that have not been computed. So the outer loop iterates over interval length, ascending, and j is derived as i + length. The peg: "short before long."

The shape-of-the-code peg is three nested loops in a fixed order: length, then left end, then split point. Three fors, in that sequence, every time. If you find yourself writing for i on the outside, you have reverted to the grid habit from L40 and the table will be full of zeros where real answers belong.

The complexity falls straight out of the shape: O(n^2) cells times O(n) split points is O(n^3). If someone asks the cost and you can see three loops, you can answer without deriving anything.

What interviewers actually ask

Interval DP is rare in a standard 45-minute screen and common in senior loops and in companies that use a hard DP as a differentiator. Nobody expects you to invent Burst Balloons on the spot; they expect you to recognise the family and articulate the inversion.

• 312 · Burst Balloons (Hard) — Google, Amazon, Meta. Probing whether you notice the first-split coupling and reverse to last. Follow-up: state the O(n^3) bound and why the sentinels remove all edge cases.
• 1547 · Minimum Cost to Cut a Stick (Hard) — Google, Amazon. Probing the sentinel-padding move and a cost term that does not depend on k. Follow-up: why sorting the cut positions is mandatory rather than convenient.
• 1039 · Minimum Score Triangulation of Polygon (Medium) — Google. The friendliest member of the family; often used as the warm-up before 312.
• 516 · Longest Palindromic Subsequence (Medium) — Amazon. Probing that palindromic DP is interval DP: dp[i][j] over ranges, filled short before long.
• 1000 · Minimum Cost to Merge Stones (Hard) — Google. Probing a third state dimension (how many piles remain), which is the real step up from 312.
• 546 · Remove Boxes (Hard) — Google, Meta. The hardest commonly-asked member; needs a third dimension counting attached duplicates.
• 877 · Stone Game and 1140 · Stone Game II (Medium) — Amazon, Google. Interval DP wearing game-theory clothing, where the value is a score difference rather than a total.

What is actually being probed in every one of these is whether you can say out loud why the obvious split fails before you write anything. Candidates who jump straight to the correct recurrence without narrating the failed one often read as having memorised the problem.

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.

Quiz

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.