On this page
Description
When you multiply a chain of matrices, the order of the multiplications doesn't change the result, but it hugely changes the work. For matrices of sizes 20x5, 5x50, 50x30 and 30x10, multiplying left to right costs 41,000 scalar multiplications and the best order costs 10,000. Ten matrices already have 4,862 possible orders. Interval DP finds the best one in O(n³). dp[i][j] is the cheapest way to combine items i through j, found by trying every split point k. The same idea, "solve every range by its best split", covers optimal binary search trees, bursting balloons and merging piles.
We'll go from simple to more technical:
- The pattern: dp[i][j] = min over k of dp[i][k] + dp[k + 1][j] + the cost of joining them, filled by length.
- A second flavor: when a 1D prefix DP is enough.
- Where interval DP shows up in production (query planning, expression evaluation).
- What breaks it: fill order, the join cost, greedy splits, overflow.
The approach
Java
int matrixChainMultiplication(int[] dims) { // matrix i is dims[i - 1] x dims[i], for i = 1..n
int n = dims.length - 1;
int[][] dp = new int[n + 1][n + 1]; // dp[i][j] = cheapest cost to multiply matrices i..j
for (int len = 2; len <= n; len++) { // shorter ranges first
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) { // the LAST multiplication joins (i..k) and (k+1..j)
int cost = dp[i][k] + dp[k + 1][j] + dims[i - 1] * dims[k] * dims[j];
dp[i][j] = Math.min(dp[i][j], cost);
}
}
}
return dp[1][n];
}
Python
def matrix_chain_multiplication(dims: list[int]) -> int: # matrix i is dims[i - 1] x dims[i], for i = 1..n
n = len(dims) - 1
dp = [[0] * (n + 1) for _ in range(n + 1)] # dp[i][j] = cheapest cost to multiply matrices i..j
for length in range(2, n + 1): # shorter ranges first
for i in range(1, n - length + 2):
j = i + length - 1
dp[i][j] = min(dp[i][k] + dp[k + 1][j] + dims[i - 1] * dims[k] * dims[j]
for k in range(i, j)) # the LAST multiplication joins (i..k) and (k+1..j)
return dp[1][n]
Whatever the best order is, it ends with one final multiplication joining the product of matrices i..k with the product of k + 1..j. Those two results are dims[i - 1] x dims[k] and dims[k] x dims[j], so the final step costs dims[i - 1] * dims[k] * dims[j] - the outer dimensions of the two halves. Trying every k and filling ranges in increasing length (so both halves are always ready) is the interval-DP template.
A second flavor: when a 1D prefix DP is enough
Minimum cuts to split a string into palindromes looks like an interval problem - try every split of every range - but that's O(n^3), 8 * 10^9 steps for n = 2,000. The cuts only happen left to right, so a prefix DP suffices: cuts[i] = fewest cuts for the first i + 1 characters, trying every last palindrome s[j..i]:
Java
// isPal[j][i] precomputed in O(n^2); cuts[i] = min over j with isPal[j][i] of (j == 0 ? 0 : cuts[j - 1] + 1)
Python
# is_pal[j][i] precomputed in O(n^2); cuts[i] = min over j with is_pal[j][i] of (0 if j == 0 else cuts[j - 1] + 1)
That's O(n^2) - about 4 million steps. Interval DP is needed when the combining step depends on both halves as ranges (like the matrix dimensions); when pieces are simply laid end to end, a prefix DP is enough.
Where you'll see it
Database query optimizers choose join orders with the same idea (dynamic programming over subsets or ranges of tables, as in the classic System R optimizer), tensor libraries pick contraction orders for chains of matrix and tensor products (numpy.einsum_path), and compilers and parsers use interval DP (CYK parsing, optimal binary search trees built from access frequencies).
Which tool for which job?
| You need | Use |
|---|---|
| The cheapest way to combine a range | interval DP: best split k, filled by length |
| The order itself | a split[i][j] table, printed recursively |
| Pieces laid end to end (palindrome cuts) | a 1D prefix DP, O(n²) |
| "Burst" or "remove" problems | choose the LAST item removed in each range |
| Cubic too slow, costs well-behaved | Knuth's optimization, O(n²) |
| Easiest correct first version | top-down memoization of best(i, j) |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Filling ranges in the wrong order | reads unsolved sub-ranges | by increasing length |
| The wrong join cost | wrong totals | dims[i - 1] × dims[k] × dims[j] |
| Cheapest adjacent pair first | 30,000 instead of 10,000 | try every split |
int totals | 98 × 500³ wraps to -634901888 | long |
| Choosing the FIRST balloon to burst | the two halves aren't independent | choose the last one |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why does the final multiplication of the range i..j at split k cost dims[i - 1] * dims[k] * dims[j]?
Show answer
The left half multiplies out to a dims[i - 1] x dims[k] matrix and the right half to dims[k] x dims[j]. Multiplying a p x q matrix by a q x r one takes p * q * r scalar multiplications.
2. For dims [20, 5, 50, 30, 10], how do left-to-right, cheapest-pair-first and the DP compare?
Show answer
41,000, 30,000 and 10,000. Neither simple rule finds the optimum; the DP tries every final split of every range.
3. Why can palindrome min-cuts use an O(n^2) prefix DP while matrix chain needs O(n^3) interval DP?
Show answer
Palindrome pieces are just laid end to end, so the best answer for a prefix depends only on where its last piece starts - one index. Matrix chain's final step cost depends on both halves' outer dimensions, so every range and every split point matter.
Key takeaways
- Interval DP: dp[i][j] for every range, built from sub-ranges, trying every split k.
- Fill ranges by increasing length so both halves are ready.
- For matrix chains, the final multiply costs the outer dimensions: dims[i - 1] * dims[k] * dims[j].
- Greedy orders fail; there are Catalan-many parenthesizations, and DP handles them in O(n^3).
- If pieces are only laid end to end, a prefix DP (O(n^2)) is enough.