DP X — Interval DP

Review boundary and corrected contracts

Choose the last event to keep interval boundary neighbors fixed. The length-first order is sufficient, not necessary: descending left endpoints can also work. The number of split trials is Θ(n³), not exactly n³; no machine-independent language/runtime cutoff follows. Burst Balloons assumes nonnegative values.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Write the three-loop interval DP skeleton from memory, and internalise the reversal that makes Burst Balloons tractable: choose the LAST burst to keep balloon neighbours fixed; other interval problems may split on a first operation instead.

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

Prerequisites. L33–L35 (state, recurrence, memo to table) and comfort with 2D tables from L40. This is the hardest DP family in the series — do not attempt it before those.

Watch first

Optional resources retained from the original lesson; video availability and contents were not rechecked in this review. The worked explanations below are self-contained.

• Burst Balloons — Dynamic Programming — Leetcode 312 — NeetCode.
• Matrix Chain Multiplication using Dynamic Programming — Abdul Bari.
• Matrix Chain Multiplication — Tushar Roy.

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. An outer loop over interval length, one valid dependency order.
2. The derivation of j from i and the length.
3. For the open-interval convention below, the inner loop for k in range(i + 1, 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 under a tight review 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. Order-dependent adjacency is a useful cue, not a theorem that greedy is impossible or that independent costs always admit a greedy solution.

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]. Length-first respects those dependencies. Descending i with ascending j also works: dp[i][k] is earlier in the same row and dp[k][j] is in a completed larger-i row.

This is a recurrence skeleton, not a standalone function: supply cost(i, k, j) for the chosen problem. Boundaries are numbered 0 through n (n >= 1), and adjacent boundaries enclose nothing. The split must make independent subproblems; a cost callback alone cannot guarantee that.

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.

Sentinel padding is not optional decoration here. Prepend and append a 1 to the array so that nums[i] and nums[j] always exist even when the range touches the edges. Without sentinels you need branch cases for "no left neighbour" and "no right neighbour" inside the innermost loop, and those branches are where the bugs go. One line of padding removes them all.

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. For N actual balloons, the exact number of split trials in maxCoins is C(N+2, 3): one trial for every triple i < k < j of padded indices. N=500 gives 20,958,500 trials, not 125 million. Each trial performs several operations, and no language-independent timing cutoff follows.
2. Operations remove or merge adjacent elements, and removal changes adjacency. Bursting, cutting, merging stones, multiplying matrices. If removing an element makes two others become neighbours, check whether a proposed greedy choice preserves the optimum; adjacency alone does not settle it.
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 a reviewer 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] through the table's upper triangle. With sentinels, vals = [1, 3, 1, 5, 1]. Adjacent boundaries enclose no balloon, so those base cells stay 0; a length-2 span encloses one balloon and is the first band the loop fills. 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. With the left boundary on the row axis and the right boundary on the column axis, that full-range answer is the top-right cell, not a diagonal cell. Each longer band combines answers from shorter bands already filled.

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.

For the matrix-chain recurrence, matrices A_i through A_j have compatible dimensions d[i-1]×d[i], ..., d[j-1]×d[j]. Choose the last multiplication between A_i..A_k and A_(k+1)..A_j: minimise M[i][k]+M[k+1][j]+d[i-1]×d[k]×d[j], with M[i][i]=0. The indices differ from the balloon open-interval template because matrices are inclusive objects and k splits between them. For dimensions [10, 30, 5, 60], (A1 A2) A3 costs 1500+3000=4500, versus 9000+18000=27000 for A1 (A2 A3).

For polygon triangulation, let T[i][j] be the best score for vertices i through j, with T[i][i+1]=0. Choose triangle (i,k,j) incident to boundary edge (i,j), and minimise T[i][k]+T[k][j]+v[i]×v[k]×v[j] over interior k. That triangle separates independent subpolygons; this is a geometric split, not a rule to execute every interval problem's last operation.

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

An invalid dependency order. Increasing left endpoints before shorter suffix intervals are computed can read unfilled cells. Length-first avoids that; descending left endpoints is also valid.

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 can work with a consistent inclusive-interval convention, but adds boundary conditionals inside the hottest code path. Pad the array instead.

Choosing the first balloon instead of the last in this recurrence. This is a conceptual failure, not a coding one. Stick cutting instead splits at the first cut, which separates the two pieces immediately. 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.

Myth: Burst Balloons should be solvable greedily — burst the smallest-value balloon first, since it contributes least and removing it lets its bigger neighbours multiply together.

Why: Try [3, 1, 5] by hand. Greedy-smallest bursts the 1 first for 3*1*5 = 15, then 3 for 1*3*5 = 15, then 5 for 1*5*1 = 5, totalling 35. That happens to be optimal here, which is exactly the danger — the heuristic looks validated. On [1, 5, 8], smallest-first earns 5 + 40 + 8 = 53. Bursting 5, then 1, then 8 earns 40 + 8 + 8 = 56, the optimum. Largest-first earns 40 + 5 + 1 = 46. These concrete counterexamples refute the two heuristics; merely lacking an exchange proof would not prove that every greedy algorithm is impossible.

Steps 1: Because bursting a balloon makes its two neighbours adjacent, the score of a later burst depends on which earlier bursts happened — the operations are not independent.

Steps 2: Because choosing the FIRST burst in a range leaves two sub-ranges whose boundaries depend on each other's outcomes, that framing does not decompose into independent subproblems.

Steps 3: Because the LAST balloon burst in a range has, by definition, nothing left beside it inside the range, its neighbours are exactly the two fixed boundaries of that range.

Steps 4: Because those boundaries are fixed and known before solving the range, the cost of the last burst is a constant expression, and the two remaining sub-ranges never interact.

Steps 5: Because each of the O(n^2) ranges tries O(n) split points doing constant work, the total is O(n^3).

Steps 6: The split-trial count grows cubically; C(202,3)/C(102,3) is about 7.88. Wall-clock ratios need measurement and are not established by this count.

Picture: A row of dominoes standing between two walls that never fall. You are not asking which domino topples first. You are asking which one is the last one standing — because at that instant you know exactly what is beside it: the two walls. Then the same question recurses on the gap to its left and the gap to its right, each with its own pair of walls.

Trigger: Consider it when adjacency-sensitive operations admit independent subintervals and the actual constraints can afford the derived trial count.

Name: Bottom-up table, length-ordered loops

Gain: No recursion depth risk; the fill order is explicit and auditable; avoids recursive calls and memo-cache lookups

Cost: You must choose a dependency-respecting order; reading an unfilled cell can fail silently

Name: Top-down memoised recursion

Gain: The recurrence reads exactly like the mathematical definition, so it is much easier to derive under pressure; fill order is handled for you automatically

Cost: O(n) recursion depth may hit the runtime stack limit; recursive calls and memo-cache lookups add overhead

Pick: Use top-down memoisation while you are still deriving the recurrence, because getting the definition right matters more than constant factors. Convert to the bottom-up table only if you hit a time-limit failure or a reviewer explicitly asks for the iterative form. Choose using the actual stack and resource limits; there is no universal n=300 crossover.

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. For Burst Balloons, splitting on the first burst 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."

Length-first is one dependency-respecting evaluation order. An outer loop over left endpoints descending and inner loop over right endpoints ascending also works; increasing-left row-major order generally does not.

The complexity falls straight out of the shape: O(n^2) cells times O(n) split points is O(n^3). Count the valid (i, k, j) triples rather than inferring a bound solely from the number of syntactic loops.

What reviewers 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. Use these as practice selections, not guarantees about what an interviewer will expect.

• 312 · Burst Balloons (Hard) — Practice selection. 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) — Practice selection. 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) — Practice selection. The friendliest member of the family; often used as the warm-up before 312.
• 516 · Longest Palindromic Subsequence (Medium) — Practice selection. Probing that palindromic DP is interval DP: dp[i][j] over ranges, filled short before long.
• 1000 · Minimum Cost to Merge Stones (Hard) — Practice selection. Probing a third state dimension (how many piles remain), which is the real step up from 312.
• 546 · Remove Boxes (Hard) — Practice selection. The hardest commonly-asked member; needs a third dimension counting attached duplicates.
• 877 · Stone Game (Medium) uses an interval score-difference state. 1140 · Stone Game II (Medium) is a related game DP, but a natural state is (start index, M), with M controlling how many piles may be taken; it is not this two-boundary split skeleton.

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: Θ(n³). Summing split positions over all intervals gives a cubic number of trials, with constants smaller than blindly multiplying n³. Measure against actual constraints rather than promising that one programming language passes and another fails.

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.

You can now…

• Recognise interval DP from a contiguous range consumed by operations whose cost depends on current neighbours.

• Explain out loud why splitting on the FIRST operation couples the two halves and breaks the recurrence.

• Reframe on the LAST operation so the split point's neighbours are exactly the two fixed boundaries.

• Write the three-loop skeleton — length, left end, split — cold, deriving j from i and the length.

• Pad with sentinels so out-of-range neighbours need no special-casing.

• State O(n^3) time and O(n^2) space directly from the loop shape.

• Name the family members — matrix chain, stick cutting, polygon triangulation — and see them as the same skeleton.

Quiz

Self-check (answer follows each question).

Q: Why does length-first work, and what left-endpoint order also works?

A: Both split intervals are shorter, so length-first works. Descending i with ascending j also works: dp[i][k] is earlier in that row and dp[k][j] is in a completed row. Increasing-i row-major order does not have that guarantee.

Q: In Burst Balloons, why does choosing the last balloon in a range work when choosing the first does not?

A: The last balloon's neighbours at burst time are exactly the range boundaries, since everything inside is already gone. That makes its cost a fixed expression and leaves two genuinely independent sub-ranges. Choosing first leaves sub-ranges whose boundaries depend on each other.

Q: What do the sentinel 1s at each end of the array accomplish?

A: They give every interior balloon a guaranteed left and right neighbour value, eliminating all boundary conditionals inside the innermost loop, and they make the answer the single cell dp\[0]\[n-1].

Q: What constraint size signals interval DP, and why?

A: A few hundred elements may make cubic work plausible, but is only a cue. Count actual split trials, check the resource limits and establish independent subintervals before choosing the method.

Q: Why can interval DP not use a rolling-array space optimisation like the two-string grid can?

A: The grid recurrence reaches back a fixed one row, so two rows suffice. Interval DP reads dp\[i]\[k] and dp\[k]\[j] for all k in the range — cells spread across the entire triangle, at arbitrary distance. There is no bounded window to roll.

Q: Minimum Cost to Cut a Stick has a cost term that does not depend on k at all. Why, and what does that tell you?

A: The cost of cutting a piece is its full current length, which is determined by the two boundaries i and j regardless of where inside you cut. It tells you the split point only affects the subproblems, not the immediate cost — so the structure is still interval DP but the cost term factors out of the inner minimum. Here k is the FIRST cut of the current piece; unlike balloons, that first operation immediately creates independent pieces.

Stretch: For stick length 7 and cuts [1, 3, 4, 5], sort and pad to [0, 1, 3, 4, 5, 7]. Set cost(i,j)=0 for adjacent boundary indices; otherwise minimise cost(i,k)+cost(k,j)+positions[j]-positions[i] over i < k < j. Cutting at 3, then 1, then 5, then 4 costs 7+3+4+2=16. These are current piece lengths, not distances to the next cut.

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.

• Three loops: interval length, left endpoint, split point is one valid order; descending left endpoints with ascending right endpoints also works.

• For Burst Balloons, choose the LAST burst so the two sub-ranges have fixed boundaries. For stick cutting, the FIRST cut separates independent pieces.

• Sentinel-pad the array so boundary neighbours always exist — it deletes every conditional from the inner loop.

• Constraints around n = 100 to 500 on an adjacency-sensitive array problem is the loudest interval-DP tell there is.

• There is no rolling-array space optimisation here; the recurrence reads across the whole triangle.

• Derive it top-down with memoisation, then convert to bottom-up only if you need the constant factor.

Corrective source notes

• Introduction to Dynamic Programming - Algorithms for Competitive Programming — Memoization stores subproblem results so repeated states need not be recomputed. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.