Algorithms from zero
Interval DP: matrix chain and the last-action split
Every DP so far has had a state that walked along one moving edge: fib(n) shrinks n, the grid path counts cells up to (row, col). This lesson’s state grabs a whole slice of the input and asks a question about it: “what is the best you can do on the chunk from index i to index j?” That is interval DP, and it has a signature move. To solve a slice, you guess the last decision made inside it—where to split it, or which element to handle last—try every guess, and glue the two smaller slices together. Because every smaller slice must already be solved, you fill the table by interval length, shortest first. This is the shape behind matrix chain multiplication and burst balloons, two problems that look impossible until the split-point idea clicks.
After this lesson you can recognize an interval DP by its state: dp[i][j] = the best answer for the subinterval [i..j] of the input. You can write the core recurrence—dp[i][j] = best over a split point k of dp[left] (combine) dp[right] + cost(i, k, j)—and explain why the answer for a slice is built from strictly smaller slices (optimal substructure). You can implement matrix chain multiplication, which minimizes the scalar multiplications needed to multiply a chain of matrices, with the recurrence dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]. You understand the iteration order: loop over interval length from short to long, then over the start index, so every sub-slice is already computed before you need it. You know the complexity—O(n^3) time (n^2 states times O(n) split choices), O(n^2) space. Finally you can frame burst balloons by thinking about the last balloon to pop inside an interval, the same split idea wearing a different hat. This is the last lesson of the unit; it is also the hardest DP shape you will meet here.
The state is a slice, not a point
In interval DP the state is a contiguous range of the input. We write dp[i][j] for the best answer achievable on the elements from index i through index j inclusive—the slice [i..j]. A single element [i..i] is the smallest slice; the full array [0..n-1] (or [1..n]) is the goal. Everything in between is a sub-slice.
The recurrence: guess the last action, split, combine
You cannot solve a slice directly, so you guess the one decision that breaks it into independent pieces. Usually that decision is a split point k: cut [i..j] into a left part and a right part, solve each, and add the cost of joining them.
dp[i][j] = best over all valid split points k of:
dp[ left slice ] (combine) dp[ right slice ] + cost(i, k, j)The two sub-slices are strictly shorter than [i..j], so they are smaller subproblems. That is the optimal substructure that makes DP legal: the best answer for the whole slice is composed from the best answers for its parts. You try every split k and keep the best, because you do not know in advance where the optimal cut is.
Why you iterate by interval length
Here is the part that trips people up. To compute dp[i][j] you read dp values for shorter slices. So those shorter slices must already be filled in. The clean way to guarantee that is to loop over the interval length from short to long:
for length = 1, 2, 3, ... up to n: // outer: how big is the slice
for i = each valid start: // inner: where does it start
j = i + length - 1 // its end
fill dp[i][j] from already-done shorter slicesBy the time length reaches some value, every slice of every smaller length is done. Looping by i then j directly would read cells that are not ready yet. Length-first is the correctness backbone of interval DP.
The diagonal fill order
Picture the DP table with rows i and columns j. Only the upper triangle where i <= j is used. Length-first iteration fills it diagonal by diagonal, starting on the main diagonal (slices of length 1) and moving outward toward the top-right corner (the full interval):
j=1 j=2 j=3 j=4
i=1 0 -> 1 -> 2 -> 3 <- final answer at dp[1][4]
i=2 0 -> 1 -> 2
i=3 0 -> 1
i=4 0
(numbers = the diagonal / interval length - 1; arrows = fill order)Each cell depends only on cells to its left (same row) and below it (same column)—all of which sit on earlier diagonals.
Canonical example: matrix chain multiplication
You want to multiply matrices A_1 * A_2 * ... * A_n. Matrix multiplication is associative—the result is the same however you parenthesize—but the cost is not. Multiplying a p x q matrix by a q x r matrix costs p*q*r scalar multiplications and produces a p x r matrix. The chain’s dimensions are stored in one array p[0..n], where matrix A_i is p[i-1] x p[i].
The last multiplication in any parenthesization splits the chain A_i..A_j into (A_i..A_k) and (A_k+1..A_j) for some k. The left product is p[i-1] x p[k], the right is p[k] x p[j], and joining them costs p[i-1]*p[k]*p[j]. So:
dp[i][j] = min over k in [i, j-1] of
dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]
dp[i][i] = 0 (a single matrix needs no multiplication)Walked through on a small chain
Take dimensions p = [40, 20, 30, 10, 30], i.e. four matrices: A_1 is 40x20, A_2 is 20x30, A_3 is 30x10, A_4 is 10x30. Fill by length:
length 2 (single split each):
dp[1][2] = 40*20*30 = 24000
dp[2][3] = 20*30*10 = 6000
dp[3][4] = 30*10*30 = 9000
length 3 (try each k):
dp[1][3] = min( k=1: 0+6000 +40*20*10=8000 -> 14000,
k=2: 24000+0 +40*30*10=12000 -> 36000 ) = 14000
dp[2][4] = min( k=2: 0+9000 +20*30*30=18000 -> 27000,
k=3: 6000+0 +20*10*30=6000 -> 12000 ) = 12000
length 4 (the whole chain):
dp[1][4] = min( k=1: 0+12000 +40*20*30=24000 -> 36000,
k=2: 24000+9000 +40*30*30=36000 -> 69000,
k=3: 14000+0 +40*10*30=12000 -> 26000 ) = 26000The minimum is 26000, achieved by splitting at k=3: multiply (A_1 A_2 A_3) first, then times A_4. A naive left-to-right order would have cost more. The split point is the whole game.
Matrix chain multiplication, length-first
The dimensions live in p, 1-indexed matrices A_1..A_n. dp[i][j] is the minimum scalar multiplications for the sub-chain A_i..A_j. Note the loop nesting: length outer, start i inner, split k innermost.
1
function matrixChain(p) {
2
const n = p.length - 1; // number of matrices A_1..A_n
3
const dp = []; // dp[i][j] = min mults for A_i..A_j
4
for (let i = 0; i <= n; i++) dp.push(new Array(n + 1).fill(0));
5
6
// build by increasing chain length so sub-chains are ready
7
for (let len = 2; len <= n; len++) {
8
for (let i = 1; i <= n - len + 1; i++) {
9
const j = i + len - 1;
10
dp[i][j] = Infinity;
11
for (let k = i; k < j; k++) { // try every split A_i..A_k | A_k+1..A_j
12
const cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
13
if (cost < dp[i][j]) dp[i][j] = cost;
14
}
15
}
16
}
17
return dp[1][n];
18
}
- L2 n matrices from a dimensions array of length n+1: A_i is p[i-1] x p[i].
- L4 dp[i][i] stays 0 - a single matrix needs no multiplication. Only i <= j is used.
- L7 Outer loop is interval LENGTH, short to long, so shorter sub-chains are already solved.
- L8 Inner loop is the start index i; the end j is forced by i + len - 1.
- L10 Reset to Infinity before minimizing over all split points.
- L11 Try every split k: left chain A_i..A_k, right chain A_k+1..A_j.
- L12 Cost = solve left + solve right + join cost p[i-1]*p[k]*p[j].
- L13 Keep the cheapest split. dp[i][j] ends as the minimum over all k.
Key point: shorter slices first, never read an unfilled cell
The whole correctness of this code rests on one ordering fact: when we compute dp[i][j], both dp[i][k] and dp[k+1][j] cover strictly shorter chains, so the length-first outer loop has already filled them. Swap the loops to iterate i then j directly and you would read cells that are still 0 (unfilled), silently producing wrong answers.
Running it on the example chain
Same chain as the walkthrough: p = [40, 20, 30, 10, 30]. The answer is 26000.
A naive analysis would suggest just multiplying left to right, but the optimal parenthesization here cuts the work by trying every split and keeping the minimum—exactly what interval DP does.
Watch the table fill diagonal by diagonal for p = [40, 20, 30, 10, 30]. Length-2 slices fill first (one split each), then length-3, then the whole chain. Each step shows the cell being written and the running set of solved cells.
1
for (let len = 2; len <= n; len++) {
2
for (let i = 1; i <= n - len + 1; i++) {
3
const j = i + len - 1;
4
for (let k = i; k < j; k++)
5
cost = dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j];
6
}
7
}
Time: O(n^3)
Count it from the loops, which mirror the DP structure exactly:
- There are O(n^2) states: one
dp[i][j]for each pairi <= j(the upper triangle of an n x n table). - Filling each state tries every split point k in the range
[i, j-1], which is up to O(n) choices, each O(1) work.
States times work-per-state = O(n^2) x O(n) = O(n^3). The three nested loops—length, start, split—are exactly these three factors. For the 4-matrix example that is a tiny constant; for n = 100 matrices it is on the order of a million operations, still instant, but the cubic growth matters as n climbs.
Space: O(n^2)
The table stores one value per state, and there are O(n^2) states (the upper triangle). That is O(n^2) space. Unlike linear DPs (Fibonacci, climbing stairs) you cannot shrink interval DP to O(1) or O(n) rows, because computing one cell can reach back to many earlier diagonals, not just the previous row—you need the whole triangle live.
states work/state time space
linear DP O(n) O(1) O(n) O(n) or O(1)
2-D grid DP O(n^2) O(1) O(n^2) O(n^2) or O(n)
interval DP O(n^2) O(n) splits O(n^3) O(n^2) <- this lessonWhy length-first is mandatory, not a style choice
The recurrence reads dp[i][k] and dp[k+1][j], both covering shorter intervals than [i..j]. A correct fill order must complete all shorter intervals before any longer one. Iterating by increasing length does that automatically: every cell of length L depends only on cells of length < L, which were finished on earlier passes. Iterate naively by i ascending then j ascending and you would compute, say, dp[1][4] while dp[2][4] (longer-reaching dependency on the same row’s right side) is unfinished—reading a stale 0 and returning a wrong, too-small cost. Length-first is the only ordering that respects the dependency, which is why every interval DP you write will have length as its outer loop.
What does the state dp[i][j] represent in an interval DP?
In the matrix chain recurrence dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + cost, what is k?
Why must interval DP iterate by increasing interval length (length outer loop)?
What is the time complexity of the matrix chain / interval DP described here?
In burst balloons, what 'last action' makes the interval split cleanly into independent sub-intervals?
Multiplying a single matrix (a sub-chain of length 1, dp[i][i]) costs how many scalar multiplications?
For dimensions p = [40, 20, 30, 10, 30], what is dp[2][3] = p[1]*p[2]*p[3] (the cost to multiply A_2 by A_3)?
Why this works
Why “guess the last action” works. Interval DP needs the slice to break into independent pieces. The trick is to fix the one decision that does the breaking and try all its options. In matrix chain that decision is the outermost (last) multiplication—choosing its split point k makes the left and right sub-chains independent, each a smaller interval. In burst balloons it is the last balloon popped inside the interval—once it is last, the rest of the interval is already empty, so its neighbors are the fixed borders. Both are the same idea: name the final action, and the leftover problem cleanly halves into two intervals you have already solved.
Common mistake
Mistake: iterating by start/end instead of by length. The single most common interval-DP bug is looping for i ... for j ... and computing dp[i][j] before all shorter slices are done. The code runs without crashing—it just reads cells that are still at their initial 0 and returns a wrong (usually too-small) answer. Always make interval length the outer loop, then derive j = i + len - 1. If you ever see an interval DP whose outer loop is the start index, suspect a dependency bug.
Edge cases
Off-by-one in the dimensions array. Matrix chain uses p of length n+1 for n matrices, where A_i is p[i-1] x p[i]. The join cost p[i-1]*p[k]*p[j] mixes three different indices, and it is easy to slip one. Sanity check with a length-2 chain: dp[i][i+1] must equal p[i-1]*p[i]*p[i+1], the only way to multiply two matrices. The base case dp[i][i] = 0 (single matrix) and the requirement i <= j (only the upper triangle is meaningful) round out the edges.
More practice
Burst balloons, framed as last-action interval DP. You have balloons with values; popping balloon i earns nums[left]*nums[i]*nums[right] where left/right are its current neighbors, then it is removed. Maximize total coins. Pad the array with virtual 1s at both ends. Let dp[i][j] = max coins from popping every balloon strictly between borders i and j. Guess k as the last balloon popped in that open interval: when it pops, i and j are its neighbors, so its reward is nums[i]*nums[k]*nums[j], and the two sub-intervals (i, k) and (k, j) are independent: dp[i][j] = max over k of dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]. Fill by interval length, same O(n^3). Notice it is “last action,” not “split point”—but the machinery is identical.
Explain what interval DP is, its recurrence, why it iterates by interval length, the matrix chain example, and its complexity.
Interval DP has a state that is a slice of the input: dp[i][j] = the best answer for the subinterval [i..j].
The recurrence: guess the last decision inside the slice—a split point k (or the last element handled)—which breaks it into two strictly shorter, independent sub-intervals, then combine and add the join cost:
dp[i][j] = best over k of dp[left] (combine) dp[right] + cost(i, k, j)Iteration order: loop over interval length short to long, then over the start index, then over the split point. Length-first is mandatory because every cell reads only shorter slices, which must already be filled.
Matrix chain multiplication (the canonical case): minimize scalar multiplications for A_1..A_n, where A_i is p[i-1] x p[i]:
dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]
dp[i][i] = 0Burst balloons is the same shape with a twist: instead of a split point, guess the last balloon popped in the interval—once it is last, its neighbors are the interval’s fixed borders and the two sides are independent.
Complexity: O(n^2) states times O(n) split points each = O(n^3) time, O(n^2) space.
That closes the dynamic programming unit. You have climbed from a single moving index (Fibonacci) to a 2-D grid to a slice of the input with an inner split loop—the full range of DP state shapes a senior engineer reaches for.