Hard Problemsminimizationinterval

Matrix Chain Multiplication

Given the dimensions of a chain of matrices that must be multiplied together in a fixed left-to-right order, find the minimum number of scalar multiplications needed by choosing where to place the parentheses, without reordering the matrices themselves.

Do this lesson first: coin change

Example input

dims = [4, 2, 3, 1, 3], so A is 4×2, B is 2×3, C is 3×1 and D is 1×3

Expected output

26 scalar multiplications, grouped as ((A(BC))D)

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i][j] is the fewest scalar multiplications needed to multiply matrices i through j, both included, down to one matrix. Matrix m is dims[m] × dims[m + 1], and the matrices are lettered A, B, C, ... from 0, so dp[1][3] is the chain BCD. Whatever the grouping, the product of matrices i..j is always dims[i] × dims[j + 1]; only the cost of getting there varies, which is why a chain's best cost can be worked out once and reused by every longer chain around it. Two numbers name the state, where the chain starts and where it ends, so only the upper triangle, i <= j, means anything, and the answer for the whole chain sits in the top-right corner, dp[0][n - 1].

dp[i][i] = 0, and for i < j, dp[i][j] = min over k from i to j - 1 of dp[i][k] + dp[k + 1][j] + dims[i] × dims[k + 1] × dims[j + 1]

However the chain i..j is bracketed, it ends with ONE last multiplication, joining the product of i..k on the left with the product of k + 1..j on the right, for some k from i to j - 1. Those two products are dims[i] × dims[k + 1] and dims[k + 1] × dims[j + 1] no matter how each was built, so that last multiplication costs dims[i] × dims[k + 1] × dims[j + 1], and each side should be built as cheaply as possible on its own: a side built any dearer could be swapped for its cheapest grouping without changing the shapes the last multiplication sees. That is dp[i][k] + dp[k + 1][j] + dims[i] × dims[k + 1] × dims[j + 1] for this k, and since you do not know which k the best grouping ends with, try them all and keep the smallest. Taking the minimum over the choices for one decision is the move coin change makes, derived in its lesson at /courses/dynamic-programming/coin-change. It is also the same loop over split points the convolution1d pages run, nth-catalan-number among them: there every split is summed, because each one builds different bracketings, and here only the cheapest is kept.

dp[i][i] = 0 on the diagonal: one matrix needs no multiplying. Every longer chain reads pairs: for a split after matrix k, the left side dp[i][k], in its own row to the left, and the right side dp[k + 1][j], in its own column below, both strictly shorter than the chain itself. A length-2 chain has one split, between two diagonal 0s, so its value is just the one multiplication. Filling by length, every length-2 chain, then every length-3 chain, and so on, guarantees every side is final before it is read. On the grid that is a sweep along the diagonals, out to the top-right corner.

Tabulation over n(n + 1) / 2 chains, each scanning up to n - 1 split points, (n³ - n) / 6 split points in all, so O(n³) time and O(n²) space. At 4 matrices that is 10 cells, 4 bases and 6 computes, reading 20 values, two for each of 10 split points; at 8 matrices it is 36 cells and 168 values read. Top-down memoization from dp[0][n - 1] saves nothing: every chain i..j is a side of some split of a longer chain, so the recursion reaches all of them, and it pays a call stack the loop does not.

Time O(n³)Space O(n²)

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[i][i] = 0 on the diagonal: one matrix needs no multiplying. Every longer chain reads pairs: for a split after matrix k, the left side dp[i][k], in its own row to the left, and the right side dp[k + 1][j], in its own column below, both strictly shorter than the chain itself. A length-2 chain has one split, between two diagonal 0s, so its value is just the one multiplication. Filling by length, every length-2 chain, then every length-3 chain, and so on, guarantees every side is final before it is read. On the grid that is a sweep along the diagonals, out to the top-right corner.

Rows ↓
Cols →

A 4×2

B 2×3

C 3×1

D 1×3

A 4×2

0

24

14

26

B 2×3

·

0

6

12

C 3×1

·

0

9

D 1×3

·

0

Rows ↓row i: the first matrix of the chain

Cols →column j: the last, so the cell is the fewest scalar multiplications for matrices i through j

matrix-chain-multiplication.ts

1function matrixChain(dims) {
2 const n = dims.length - 1; // matrix m is dims[m] x dims[m + 1]
3 const dp = Array.from({ length: n }, () => new Array(n).fill(0));
4 for (let len = 2; len <= n; len++) {
5 for (let i = 0; i + len - 1 < n; i++) {
6 const j = i + len - 1;
7 let best = Infinity;
8 for (let k = i; k < j; k++) {
9 const join = dims[i] * dims[k + 1] * dims[j + 1];
10 best = Math.min(best, dp[i][k] + dp[k + 1][j] + join);
11 }
12 dp[i][j] = best;
13 }
14 }
15 return dp[0][n - 1];
16}

Base caseComputedBeing readAnswer

The code, the trap, the variations

matrix-chain-multiplication.ts

1function matrixChain(dims) {
2 const n = dims.length - 1; // matrix m is dims[m] x dims[m + 1]
3 const dp = Array.from({ length: n }, () => new Array(n).fill(0));
4 for (let len = 2; len <= n; len++) {
5 for (let i = 0; i + len - 1 < n; i++) {
6 const j = i + len - 1;
7 let best = Infinity;
8 for (let k = i; k < j; k++) {
9 const join = dims[i] * dims[k + 1] * dims[j + 1];
10 best = Math.min(best, dp[i][k] + dp[k + 1][j] + join);
11 }
12 dp[i][j] = best;
13 }
14 }
15 return dp[0][n - 1];
16}

Where people go wrong

Multiplying the cheapest adjacent pair first, and repeating. It feels safe because every step it takes is small, and on this page it matches the table at 2 and 3 matrices. At 4 it fails: BC is the cheapest pair (6), and after it the chain is A (4×2), BC (2×1) and D (1×3), whose cheapest pair is BC times D (6) rather than A times BC (8). That leaves a 4×2 times 2×3 multiplication, 24, for last: (A((BC)D)) costs 36, against 26 for ((A(BC))D). A cheap step can leave wide matrices for the final multiplication, and only weighing every split point, sides and join together, sees that; at 8 matrices the greedy order costs 150 against the table's 81. The other common slip is not choosing at all and multiplying straight left to right, as a loop over the array would: 48 at 4 matrices and 268 at 8.

Report the grouping, not just its cost.
That is printing-matrix-chain-multiplication. The table and its recurrence do not change; each cell also remembers the k that won it, and a walk from dp[0][n - 1] splits there and recurses into both sides until each side is one matrix. At 4 matrices the walk prints ((A(BC))D).
Count the groupings instead of finding the cheapest.
Swap the min for a sum and drop the join cost: ways[i][j] = sum over k of ways[i][k] × ways[k + 1][j], with ways[i][i] = 1. The split loop and the fill order stay the same. What goes is any use of dims, so the count depends only on the chain's length, and it is the Catalan number nth-catalan-number fills as a 1D table: 5 groupings of 4 matrices, 429 of 8.
Find the most expensive grouping.
Replace the min with a max; the table, the reads and the order are unchanged. At 4 matrices the worst is ((AB)(CD)) at 69, and at 8 the worst costs 390, against the best's 81, which is how much the choice of brackets is worth on this chain.
Triangulate a convex polygon with the least total weight, where a triangle costs the product of its three corner values.
The same table under different names. dp[i][j] covers corners i..j, and it is the min over an apex k strictly between them of dp[i][k] + dp[k][j] + v[i] × v[k] × v[j], with dp[i][i + 1] = 0 for a bare edge. What changes is only the indexing: the two sides share corner k instead of splitting after it. A polygon whose corner values are dims gives this page's answer, 26 for corners 4, 2, 3, 1, 3.

Program for Bridge and Torch problem Printing Matrix Chain Multiplication