MATRIX-CHAIN(p[0..n]): // p[i-1] x p[i] = dim of matrix i
dp[i][j] = min cost to multiply matrices i..j
dp[i][i] = 0 // single matrix, no cost
for length = 2 to n:
for i = 1 to n-length+1:
j = i + length - 1
dp[i][j] = infinity
for k = i to j-1: // split point
cost = dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]
dp[i][j] = min(dp[i][j], cost)
§2 — The Idea, Step by Step
Start here. When you multiply a row of matrices — say $A \times B \times C$ — the final answer is always the same no matter how you group them. That is what we mean by saying matrix multiplication is associative: $(A\,B)\,C = A\,(B\,C)$. But here is the surprise that this whole page is about: the amount of work to reach that answer is not the same. Choosing where to put the parentheses is like choosing the order to combine puzzle sections — you always finish the same picture, but some orders force you to do far more fiddling along the way.
Put numbers on it. Multiplying a $p\times q$ matrix by a $q\times r$ matrix costs about $p\cdot q\cdot r$ small multiplications. A chain is described by one list of dimensions $p[0],p[1],\dots,p[n]$, where matrix $i$ has size $p[i-1]\times p[i]$. Take $A$ as $10\times30$, $B$ as $30\times5$, and $C$ as $5\times60$. Group as $(AB)C$: $10\cdot30\cdot5 + 10\cdot5\cdot60 = 1500 + 3000 = 4500$. Group as $A(BC)$: $30\cdot5\cdot60 + 10\cdot30\cdot60 = 9000 + 18000 = 27000$. Identical matrix out — six times the work in, just from where the parentheses landed.
The clever part. Testing every grouping is hopeless: the number of parenthesizations explodes like the Catalan numbers, $C(n-1)\sim 4^{\,n}/n^{3/2}$. So we build a small table instead. Let $dp[i][j]$ be the cheapest cost to multiply matrices $i$ through $j$. A lone matrix costs nothing: $dp[i][i]=0$. For a longer stretch, try every place $k$ to make the final cut and keep the best: $dp[i][j]=\min_{i\le k
Try this in the sim above. Press Next repeatedly and watch the Step and Comparisons counters tick up while the MATRIX-CHAIN recurrence stays in view on the right. Drag the $n$ slider to a longer chain and press Reset — more matrices mean a bigger $dp$ table to fill in. Then glance back at the worked example: the only thing that changed between $4500$ and $27000$ was a single pair of parentheses.
§3 — Algorithm Analysis & Derivation
Symbol
Meaning
n
Input size
T(n)
Time complexity function
W(n)
Worst-case complexity
A(n)
Average / amortized complexity
Φ(S)
Potential function of data structure state S
α(n)
Inverse Ackermann function (~constant)
Step 1 — Problem. Matrix multiplication is associative: (AB)C = A(BC). Different parenthesizations have the same result but wildly different computational costs. Given n matrices A_1 A_2 ... A_n with dimensions p[0]×p[1], p[1]×p[2], ..., p[n-1]×p[n]: find the parenthesization minimizing total scalar multiplications.
Step 2 — Cost Formula. Multiplying a (p×q) matrix by a (q×r) matrix costs p·q·r scalar multiplications. Example: A(10×30) · B(30×5) · C(5×60). ((AB)C): 10·30·5 + 10·5·60 = 1500+3000 = 4500. (A(BC)): 30·5·60 + 10·30·60 = 9000+18000 = 27000. First is 6× cheaper!
Step 3 — Recurrence. dp[i][j] = min cost to compute product of matrices i through j. dp[i][i] = 0. For i < j: dp[i][j] = min over k from i to j−1 of dp[i][k] + dp[k+1][j] + p[i−1]·p[k]·p[j]. The last term is the cost of multiplying the two resulting matrices.
Step 4 — Time O(n³) Space O(n²). Three nested loops (length, i, k): O(n³). Table dp[n][n]: O(n²). Compare with naive: the number of parenthesizations grows as Catalan numbers C(n-1) ~ 4^n/n^(3/2). DP reduces exponential to polynomial.
Step 5 — Catalan Numbers and Naive Count. For n matrices, number of distinct parenthesizations = Catalan number C(n-1) = C(2n-2,n-1)/n. C(1)=1, C(2)=2, C(3)=5, C(4)=14, C(5)=42, C(10)=16796. Grows as 4^n/n^(3/2)√π — exponential. DP avoids re-evaluating overlapping subproblems.
Step 6 — Reconstruction. Track split[i][j] = k that minimized dp[i][j]. Reconstruct: PRINT-OPT(i,j): if i==j print A_i; else print '(' PRINT-OPT(i,split[i][j]) ' x ' PRINT-OPT(split[i][j]+1,j) ')'. This gives the actual optimal parenthesization string.
§4 — Frequently Asked Questions
Why is matrix chain order important? concept+
Matrix multiplication is NOT commutative (AB ≠ BA in general) but IS associative. Different parenthesizations give the same mathematical result but vastly different numbers of operations. The optimal order can reduce computation by orders of magnitude.
Why can't we use greedy for matrix chain? concept+
Greedy approaches (always multiply cheapest adjacent pair, or use dimension ratio) fail because local optimal choices lead to globally suboptimal results. The problem requires considering all possible split points at each level — exactly what DP provides.
Where is matrix chain multiplication used? applied+
Compiler optimization for array expressions. Deep learning frameworks (PyTorch, TensorFlow) optimize the order of tensor contractions. Scientific computing with sparse/structured matrices. SQL query optimization (join ordering is analogous — minimize intermediate table sizes).
What is the connection to interval DP? complex+
Matrix chain is the canonical interval DP problem. Other interval DP problems: Optimal BST construction, Burst Balloons (LC 312), Palindrome Partitioning, Minimum cost to fill a convex polygon with triangles. All follow: dp[i][j] = optimize over split point k in [i,j-1].
Why do Catalan numbers appear? nonobv+
The number of ways to parenthesize n matrices = C(n-1) = nth Catalan number. Catalan numbers count: binary trees with n nodes, valid bracket sequences of length 2n, ways to triangulate a convex (n+2)-gon. All equivalent. The exponential growth shows why brute force is infeasible for even n=20.
Is there an O(n^2) algorithm? deep+
Hu-Shing algorithm (1982) solves matrix chain in O(n log n). Reformulates as a triangulation problem on a convex polygon. Complex to implement, rarely used in practice since O(n³) DP is fast enough for typical sizes (n < 1000). O(n log n) becomes relevant for very large chains in scientific computing.
§5 — Misconceptions & Implementation Errors
Conceptual Misconceptions
✗ Matrix chain multiplication optimizes the result value.
✓ Matrix chain optimizes the NUMBER OF OPERATIONS (computational cost), not the numerical result. All valid parenthesizations give the same matrix product — only the cost differs.
✗ The greedy approach (cheapest adjacent pair) is optimal.
✓ Greedy fails for matrix chain. Example: A(1x100) B(100x1) C(1x100). Greedy picks B·C first (cost 100·1·100=10000) then A·(BC) (cost 1·100·100=10000). Total 20000. Optimal: (A·B)·C: 1·100·1 + 1·1·100 = 100+100=200. 100x cheaper!
✗ dp[i][j] can be computed in any order.
✓ Must fill dp in order of increasing subchain LENGTH (dp[i][i+1] before dp[i][i+2], etc.). Computing dp[i][j] requires dp[i][k] and dp[k+1][j] for all k — these must be computed first.
Implementation Errors
✗ Forgetting the cost p[i-1]*p[k]*p[j] in the recurrence.
✓ The term p[i-1]*p[k]*p[j] is the cost of the FINAL multiplication (left result times right result). Forgetting it gives wrong answers — only counting sub-chain costs, missing the last merge cost.
✗ Using 0-indexed p[] without adjusting the dimension formula.
✓ If p is 0-indexed: matrices[i] has dimensions p[i-1] x p[i] (1-indexed matrices). Adjusting: matrices[i] (0-indexed) has dimensions p[i] x p[i+1]. Mixing conventions causes incorrect dimension lookups.
✗ Assuming the split point k is the middle of [i,j].
✓ The optimal split k can be anywhere in [i, j-1]. Must try ALL possible k values and take the minimum. There is no shortcut to find the optimal k without trying all options.