The site's seventh dynamic programming entry, and the first
with a genuinely different subproblem shape from all six before it: instead of a position in one or two
sequences, a cell here is indexed by a whole contiguous range of one sequence. Given a
chain of matrices A₁, A₂, …, Aₙ with compatible dimensions — each Aᵢ is
p[i-1] × p[i], so consecutive matrices always share an inner dimension — matrix
multiplication is associative: (A₁A₂)A₃ and A₁(A₂A₃) compute
the exact same result matrix. It is not commutative, though — the matrices must stay in the same
left-to-right order, only the grouping (where the parentheses go) is free to change. That
grouping choice doesn't affect the answer, but it can change the number of scalar multiplications needed
to get there by an order of magnitude. Matrix Chain Multiplication finds the grouping that minimizes
that cost.
Four fixed matrices, dimensions A₁: 10×30, A₂: 30×5, A₃: 5×60,
A₄: 60×10 — encoded as one dimension array p = [10, 30, 5, 60, 10], where
Aᵢ is p[i-1] × p[i]. Press Step or Run to
watch the table fill in by increasing chain length: first every length-2 product (adjacent pairs), then
length-3, then the full length-4 chain, each cell trying every internal split point and keeping the
cheapest. Once the table is full, the demo walks back down from the top (the whole chain) through the
recorded split points, revealing the actual optimal parenthesization one grouping at a time.
chain
dp[i][j] — cheapest cost to multiply Aᵢ…Aⱼ as one group
Multiplying an r×c matrix by a c×s matrix takes r·c·s scalar
multiplications — one per entry of the r×s result, each a dot product of length
c. dp[i][j] holds the cheapest cost of computing the product
Aᵢ···Aⱼ as a single matrix. The base case is a lone matrix: dp[i][i] = 0, no
multiplication needed at all. For a range longer than one matrix, the last multiplication that
happens is always between some left group Aᵢ···Aₖ and some right group
A_{k+1}···Aⱼ, for some split point k between i and
j - 1 — every possible grouping is exactly one choice of where that final split falls.
Trying every k and keeping the best gives the recurrence:
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]dp[i][k] and dp[k+1][j] are the costs already paid to reduce each side to a
single matrix; p[i-1] * p[k] * p[j] is the cost of that final multiplication, since the left
group's result is p[i-1] × p[k] and the right group's is p[k] × p[j]. Every
subproblem a cell needs is a shorter range than itself, so filling the table by increasing chain
length — every length-2 range first, then every length-3 range, and so on — guarantees both pieces are
already sitting in the table by the time a cell needs them. On the demo chain, the table looks like:
| j=1 | j=2 | j=3 | j=4 | |
|---|---|---|---|---|
| i=1 | 0 | 1500 | 4500 | 5000 |
| i=2 | · | 0 | 9000 | 4500 |
| i=3 | · | · | 0 | 3000 |
| i=4 | · | · | · | 0 |
dp[1][4] = 5000 is the answer for the whole chain, reached by splitting at
k=2: dp[1][2] + dp[3][4] + p[0]·p[2]·p[3] = 1500 + 3000 + 10·5·10 = 5000, cheaper
than either splitting at k=1 (0 + 9000 + 10·30·10 = 12000) or k=3
(4500 + 0 + 10·60·10 = 10500).
Builds the table bottom-up by chain length, recording each cell's winning split point alongside its cost, then recovers the actual parenthesization by walking the split table recursively from the top:
function matrixChainOrder(p) {
const n = p.length - 1; // number of matrices
const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
const split = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(-1));
for (let len = 2; len <= n; len++) {
for (let i = 1; i <= n - len + 1; i++) {
const j = i + len - 1;
dp[i][j] = Infinity;
for (let k = i; k < j; k++) {
const cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
if (cost < dp[i][j]) {
dp[i][j] = cost;
split[i][j] = k;
}
}
}
}
return { minCost: dp[1][n], split };
}
function buildParen(split, i, j) {
if (i === j) return `A${i}`;
const k = split[i][j];
return `(${buildParen(split, i, k)} × ${buildParen(split, k + 1, j)})`;
}Associativity means the result is always the same matrix — it does not mean the grouping is
free. Every one of the demo chain's five distinct parenthesizations computes the identical
10×10 result matrix, but their scalar-multiplication costs span a 6.6× range: ((A₁ ×
A₂) × (A₃ × A₄)) costs 5,000 (the optimum this page's demo finds), the naive
strictly-left-to-right grouping (((A₁ × A₂) × A₃) × A₄) costs 10,500 — already
more than double — and the worst of the five, ((A₁ × (A₂ × A₃)) × A₄), costs
33,000. Matrix multiplication's associativity is exactly what makes every one of those five
groupings valid; it says nothing about their relative cost. Non-commutativity is the other half of the
same trap: the matrices can never be reordered, only regrouped, since AᵢAⱼ and
AⱼAᵢ are generally not even the same shape, let alone the same values.
The table computes every subproblem, but the optimal chain only ever uses a fraction of
them. The demo chain has six ranges with i < j — (1,2),
(2,3), (3,4), (1,3), (2,4), (1,4) — and
dp fills in all six, since any of them might turn out to be the cheapest sub-piece of some
larger range. But the final reconstruction, walking down from dp[1][4] through its winning
split, only ever visits three of them: (1,4) splits into (1,2) and
(3,4), and both of those are single-matrix leaves already. (2,3),
(1,3), and (2,4) were computed and compared against, but never actually used.
That's a different backtrack shape from Longest Common Subsequence or Edit Distance, whose single path threads through most
of a 2D grid — here the "path" is a tree, and most of the table exists only to help decide it, not to sit
on it.
The dimension array is one longer than the matrix count, and mixing up the offset silently
produces the wrong cost, not a crash. With n matrices, p has
n + 1 entries — Aᵢ is p[i-1] × p[i] — so the final multiplication
in the recurrence is p[i-1] * p[k] * p[j], not p[i] * p[k] * p[j]. Swapping in
that off-by-one on this page's own reference implementation, run against the identical demo chain, still
finishes and still returns a number — just the wrong one: 13,500 instead of the correct
5,000. Every array index still stays in bounds, so nothing throws; the bug only shows up as
a plausible-looking wrong answer, confirmed directly rather than assumed.
Time: O(n³) — O(n²) ranges (i, j), each trying
up to O(n) split points. That's a real step up from every other entry in this category: Longest Common Subsequence and Edit Distance fill an equally two-dimensional table but spend
only O(1) work per cell, giving O(m·n) overall — Matrix Chain Multiplication's
extra split-point search is the cost of the range shape itself. Space: O(n²)
for the dp and split tables; unlike the two-sequence entries' single-row space
optimization, both tables are needed in full here, since the recurrence for a longer range reaches back
to ranges of every shorter length, not just the row immediately before it.
This site's guide, Choosing a Dynamic Programming Approach, compares this entry against the other ten Dynamic Programming entries side by side.