A new shape of subproblem: the segment
In the first rung of this ladder a subproblem was usually named by a prefix — 'the first i items', 'the first i characters'. That worked because the answers grew by adding one element at a time, left to right. But a whole family of problems refuses to be sliced that way: you can only make progress by merging two neighbouring pieces, and the piece you create is itself a contiguous stretch that must be merged again. For these, the natural subproblem is not a prefix but a segment — a contiguous run from position i to position j — and the technique built on it is called interval DP.
The state is therefore two-dimensional: dp[i][j] holds the best answer for the segment that runs from i to j inclusive. Naming the state this way is the same discipline you learned in defining the state — it must be sufficient (everything the future depends on is captured by the two endpoints) and minimal (nothing more). What is genuinely new is the evaluation order. A prefix DP fills left to right; an interval DP fills by increasing length, because a longer segment's answer is built only from shorter segments strictly inside it, so all of those must be ready first.
The flagship example: parenthesizing a matrix chain
Here is the problem that makes interval DP click. You must multiply a chain of matrices in a fixed left-to-right order, say A times B times C times D. Matrix multiplication is associative, so every way of parenthesizing — (A B)(C D), A((B C)D), and so on — produces the identical result matrix. But the arithmetic cost is wildly different. Multiplying a p-by-q matrix by a q-by-r matrix costs p times q times r scalar multiplications, so the order in which you collapse the chain can change the total work by orders of magnitude. The task of matrix-chain multiplication is to find the cheapest parenthesization — not to actually multiply anything.
The dimensions are captured by a single array. If the matrices are A1, A2, ..., An, let p[0], p[1], ..., p[n] be the sizes so that Ak is p[k-1]-by-p[k] — that one row of numbers encodes the whole chain. Now feel why brute force is hopeless: the number of distinct parenthesizations of n matrices is the (n-1)-th Catalan number, which grows like 4^n divided by a polynomial. Trying them all is exponential, so we want the disciplined collapse a DP gives. The key observation is that any parenthesization, however nested, has exactly one outermost multiplication — the last one performed.
The split point, and the recurrence it gives
Fix attention on the segment of matrices from i to j, and define dp[i][j] as the minimum number of scalar multiplications to compute their product. Whatever the optimal parenthesization is, its last multiplication splits the chain into a left block (matrices i through k) and a right block (matrices k+1 through j) for some split point k between i and j-1. The left block produces a p[i-1]-by-p[k] matrix, the right block a p[k]-by-p[j] matrix, and multiplying those two costs p[i-1] times p[k] times p[j]. We do not know the best k, so we try every one and keep the cheapest — and crucially, the cost of each block is itself an optimal sub-answer, dp[i][k] and dp[k+1][j], which is optimal substructure doing its job.
dp[i][j] = 0 if i == j (one matrix, nothing to multiply)
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] if i < j
answer = dp[1][n]
fill order: increasing segment length L = 1, 2, ..., n-1
for L = 1 to n-1:
for i = 1 to n-L:
j = i + L
dp[i][j] = min over k of ( dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j] )Read the transition aloud and it almost narrates itself: 'the cheapest way to multiply matrices i..j is, over all places I could make the final cut, the cost of the left block plus the cost of the right block plus the price of joining them.' The base case is dp[i][i] = 0 — a single matrix needs no multiplication at all. Notice that dp[i][j] only ever reads entries for shorter segments (both i..k and k+1..j sit strictly inside i..j whenever i < j), which is precisely why the evaluation order must go by increasing length: process all length-1 segments, then length-2, and so on, so every smaller segment a cell needs is already final.
What it costs, and why O(n^3) and not 4^n
The running time falls straight out of the table, and it is the same product you have used all along: (number of distinct states) times (work per state). There are O(n^2) segments [i, j], and computing one of them scans up to O(n) split points k, doing O(1) arithmetic at each — so the total is O(n^3). That is a stunning collapse from the Catalan-number 4^n of brute force down to a cubic polynomial: for n = 30 matrices, brute force faces astronomically many parenthesizations, while the DP does on the order of 27,000 cheap operations. The exponential blow-up was pure recomputation of the same segments, and the table recovers all of it.
One honest limit to flag now, because it shapes the rest of this rung. O(n^3) is excellent, but for some interval DPs even cubic is too slow, and people have found ways to shave it. When the cost function is well-behaved, the best split point moves monotonically as the segment grows — it never jumps backward — and exploiting that drops matrix-chain-style DPs from O(n^3) toward O(n^2) via the Knuth-Yao quadrangle inequality, or via the divide-and-conquer DP optimization. Those are real speed-ups but they rest on extra conditions that do not always hold; the plain O(n^3) recurrence above is the trustworthy default that always works.
From cost to plan: reconstructing the parenthesization
The table above answers 'how cheap can it be?' but not 'how do I actually parenthesize?' — and a number alone rarely satisfies. The fix is the standard move of reconstructing the solution: alongside dp[i][j], store a second table split[i][j] recording the k that achieved the minimum for that segment. The split table is a compact record of every decision the DP made, and from it you can recover the full parenthesization without recomputing any costs.
- While filling dp[i][j], whenever a split point k gives a strictly smaller value, record split[i][j] = k. By the end, split[1][n] holds the outermost cut of the optimal plan.
- To print the parenthesization of segment i..j, look at k = split[i][j]: if i equals j, just print matrix Ai; otherwise print an open bracket, recurse on i..k, recurse on k+1..j, then a close bracket.
- This trace touches each segment of the optimal plan once, so reconstruction is O(n) extra work on top of the O(n^3) fill — the plan is essentially free once the table exists.
This same segment-shaped pattern — state dp[i][j], a split point that names the last operation, fill by increasing length, and a split table for reconstruction — is the template you will reuse across interval DP. It powers the optimal binary search tree, where the split is the root and the cost is the expected search depth; it powers polygon triangulation, optimal string parenthesization, and 'burst balloons' style merge games. Matrix chain is simply the cleanest first instance, so the muscle memory you build here transfers directly. Next we will leave the line and put intervals aside to let subproblems live on the nodes of a tree.