Interval DP

algorithmadvancedTime O(n^3)Space O(n^2)

Some problems ask for the best way to combine a whole range, and the only sensible subproblems are shorter ranges. Interval DP fills a triangular table by length: single items first, then every pair, then every triple, so that when a range is reached both halves of any split are already known. Matrix chain multiplication picks where the last multiplication happens; merging adjacent piles picks which merge happens last. Each cell tries every split point, so the whole thing is O(n^3), and the table quietly covers an exponential number of orderings.

Multiply 4 matrices, M0 (10 x 20), M1 (20 x 30), M2 (30 x 40), M3 (40 x 30), with the fewest scalar multiplications. Multiplying a p x q by a q x r costs p x q x r. dp[i][j] is the cheapest way to multiply Mi..Mj; a single matrix costs 0, the diagonal. Longer ranges try every place for the last multiplication.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 6, with their answers.

dp[0][1] takes the cheapest split. The split costs are 6000. What goes in the cell?
- 6000
- 6001
Answer: 6000. The minimum over every k of dp[i][k] + dp[k+1][j] plus the cost of combining the two halves.
dp[1][2] takes the cheapest split. The split costs are 24000. What goes in the cell?
- 24000
- 24001
Answer: 24000. The minimum over every k of dp[i][k] + dp[k+1][j] plus the cost of combining the two halves.
dp[2][3] takes the cheapest split. The split costs are 36000. What goes in the cell?
- 36000
- 36001
Answer: 36000. The minimum over every k of dp[i][k] + dp[k+1][j] plus the cost of combining the two halves.
dp[0][2] takes the cheapest split. The split costs are 32000, 18000. What goes in the cell?
- 18000
- 32000
Answer: 18000. The minimum over every k of dp[i][k] + dp[k+1][j] plus the cost of combining the two halves.
dp[1][3] takes the cheapest split. The split costs are 54000, 48000. What goes in the cell?
- 48000
- 54000
Answer: 48000. The minimum over every k of dp[i][k] + dp[k+1][j] plus the cost of combining the two halves.
dp[0][3] takes the cheapest split. The split costs are 54000, 51000, 30000. What goes in the cell?
- 30000
- 51000
- 54000
Answer: 30000. The minimum over every k of dp[i][k] + dp[k+1][j] plus the cost of combining the two halves.

How it runs, step by step

Multiply 4 matrices, M0 (10 x 20), M1 (20 x 30), M2 (30 x 40), M3 (40 x 30), with the fewest scalar multiplications. Multiplying a p x q by a q x r costs p x q x r. dp[i][j] is the cheapest way to multiply Mi..Mj; a single matrix costs 0, the diagonal. Longer ranges try every place for the last multiplication.
Matrix chain of 4 matrices.
dp[0][1], length 2: split at 0: 0 + 0 + 6000 = 6000. Best is 6000, splitting at 0: multiply (M0..M0), a 10 x 20, by (M1..M1), a 20 x 30, for 10 x 20 x 30 = 6000.
dp 0 1 is 6000.
dp[1][2], length 2: split at 1: 0 + 0 + 24000 = 24000. Best is 24000, splitting at 1: multiply (M1..M1), a 20 x 30, by (M2..M2), a 30 x 40, for 20 x 30 x 40 = 24000.
dp 1 2 is 24000.
dp[2][3], length 2: split at 2: 0 + 0 + 36000 = 36000. Best is 36000, splitting at 2: multiply (M2..M2), a 30 x 40, by (M3..M3), a 40 x 30, for 30 x 40 x 30 = 36000.
dp 2 3 is 36000.
dp[0][2], length 3: split at 0: 0 + 24000 + 8000 = 32000; split at 1: 6000 + 0 + 12000 = 18000. Best is 18000, splitting at 1: multiply (M0..M1), a 10 x 30, by (M2..M2), a 30 x 40, for 10 x 30 x 40 = 12000.
dp 0 2 is 18000.
dp[1][3], length 3: split at 1: 0 + 36000 + 18000 = 54000; split at 2: 24000 + 0 + 24000 = 48000. Best is 48000, splitting at 2: multiply (M1..M2), a 20 x 40, by (M3..M3), a 40 x 30, for 20 x 40 x 30 = 24000.
dp 1 3 is 48000.
dp[0][3], length 4: split at 0: 0 + 48000 + 6000 = 54000; split at 1: 6000 + 36000 + 9000 = 51000; split at 2: 18000 + 0 + 12000 = 30000. Best is 30000, splitting at 2: multiply (M0..M2), a 10 x 40, by (M3..M3), a 40 x 30, for 10 x 40 x 30 = 12000.
dp 0 3 is 30000.
The cheapest order costs 30000 scalar multiplications, dp[0][3]. 6 cells were filled, each trying up to 3 split points: O(n^3) time and O(n^2) space, against the exponential number of parenthesisations it silently covered.
Minimum cost 30000.

Write it yourself

Define matrixChainCost(dims) and return the fewest scalar multiplications the chain can be done in. It runs in your browser against this lesson's own 2 examples.

1// dims of length n + 1 describes n matrices. Try every place to split the chain, and add the cost of joining the two halves.2function matrixChainCost(dims) {3  4  return 0;5}6

Ln 1, Col 16 linesTab indents; Escape then Tab leaves the editor. Ctrl-Enter runs, Cmd-Enter on a Mac.

Remember

Fill by length: dp[i][i] is the base case, and dp[i][j] needs every shorter range inside it.
dp[i][j] = min over k in i..j-1 of dp[i][k] + dp[k+1][j] + cost of combining the two halves.
n^2 cells times n split points: O(n^3) time, O(n^2) space.

Topics covered

Where this is used

Numerical computingnumpy.linalg.multi_dot

The cost of a chain of matrix products depends only on the shapes, which are known before a single number is touched, so the ordering can be solved first and the arithmetic done second. NumPy's multi_dot does exactly that: a chain of four or more goes through this DP, a chain of three is special-cased by comparing the only two parenthesisations directly, and then dot is called in the order that won. The example in NumPy's own docs is a 10x100 times a 100x5 times a 5x50: 7500 multiplications one way, 75000 the other, for the identical result.

BioinformaticsRNA secondary structure prediction

A strand folds back on itself and pairs bases, and as long as pairs do not cross, which is what these algorithms assume, a pair between positions i and j separates everything inside it from everything outside, so the subproblems are subsequences i..j. Nussinov's 1978 algorithm maximises paired bases with this same fill-by-length table, and Zuker's energy model, which is what ViennaRNA's RNAfold and mfold run, keeps the recurrence and swaps in thermodynamic costs. The n^3 is why folding a microRNA is instant and folding a viral genome is a batch job.

Language toolsCYK parsing

dp[i][j] holds the set of grammar symbols that can produce the substring from i to j, and a binary rule A -> B C is precisely a split point, with B covering i..k and C covering k+1..j. That is what makes membership in an arbitrary context-free grammar decidable in O(n^3) instead of by exponential backtracking, as long as the grammar is in Chomsky normal form. The probabilistic version is the same loop with max over k in place of min, which is what the Stanford parser's PCFG stage and NLTK's ViterbiParser both run.

Search structuresOptimal binary search trees

The subtrees of a binary search tree always hold contiguous key ranges, so picking the root for keys i..j splits them into i..k-1 and k+1..j, which makes this an interval problem rather than a subset one. When a lookup table is built once and queried forever and some keys are hit far more often than others, Knuth's 1971 algorithm builds the tree with the smallest expected number of comparisons under those frequencies. It is where the monotone split bound came from, and that bound is what brings this particular fill down to O(n^2).

Why it works this way

Why the table is filled by length and not row by row

dp[i][j] reads dp[i][k] and dp[k+1][j], and both of those ranges are strictly shorter than i..j, never longer. A plain loop over i ascending and j ascending reads cells that have not been written yet, and since they still hold 0 the answer comes out wrong without anything crashing. Filling by increasing length is the simplest order that respects that dependency; looping i downward with j upward from i works just as well. Memoised recursion sidesteps the ordering question entirely, at the cost of n deep stack frames.

Why the split is where the last combine happens, not the first

The two sides of the split have to be independent problems over contiguous ranges, or the table cannot be indexed by i and j at all. Fixing the last multiplication gives exactly that: everything in i..k collapses to one matrix, everything in k+1..j collapses to another, and neither half cares what the other chose. Fixing the first multiplication instead leaves a chain that contains a product of two originals, so the remaining state is no longer a range of the input. It is also what makes the cost term knowable: the halves collapse to a dims[i] x dims[k+1] and a dims[k+1] x dims[j+1] matrix, which is why n matrices need n+1 dimensions and why dims[k+1] is the classic off-by-one.

Greedy gets close and is still wrong

Always merging the cheapest adjacent pair is the obvious shortcut, and on the five piles in this lesson, 6 2 3 4 5, it costs 48 where the table finds 45. Huffman coding solves the same sum-of-the-two-piles cost in O(n log n), but only because it may merge any two piles; once merges must be adjacent its choice can be illegal. On 1 5 1 Huffman pairs the two 1s for a total of 9, which no legal sequence of adjacent merges can reach, since the real answer is 13. The adjacency constraint is what forces the full table.

When O(n^3) can be cut to O(n^2)

If the combine cost satisfies the quadrangle inequality, as the sum-of-the-range cost in mergeCost does, the best split point is monotone: opt[i][j-1] <= opt[i][j] <= opt[i+1][j]. Restricting k to that window makes the inner loops telescope and the whole fill drops to O(n^2). This is Knuth's optimisation, first used for optimal binary search trees. Matrix chain does not meet the condition, although Hu and Shing published a specialised O(n log n) ordering algorithm for it in 1982.