DPDynamic Programming
Matrix Chain Multiplication
Choose the parenthesization of a matrix product that minimizes scalar multiplications — the archetypal interval DP.
10
0
30
1
5
2
60
3
| A1 | A2 | A3 | |
|---|---|---|---|
| A1 | 0 | · | · |
| A2 | · | 0 | · |
| A3 | · | · | 0 |
1/9A1..A3 have shapes 10×30, 30×5, 5×60. A single matrix needs 0 multiplications, so the diagonal is 0. Only the upper triangle (i ≤ j) is used.
Cell being filledDependency readBase caseComputedReconstructed choice
PseudocodeLearn Matrix Chain Multiplication →
1dp[i][i] = 02for len in 2 .. n:3 for i in 1 .. n-len+1: j = i+len-14 dp[i][j] = ∞5 for k in i .. j-1:6 cost = dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]7 if cost < dp[i][j]: dp[i][j] = cost; split[i][j] = k8return dp[1][n]Variables
n3
Complexity
best O(n³)
avg O(n³)
worst O(n³)
space O(n²)
Speed