Hard Problemsintervalreconstruction

Printing Matrix Chain Multiplication

Given the same matrix-chain setup of dimensions in a fixed multiplication order, find the minimum scalar-multiplication cost and also report one fully parenthesized grouping of the chain that achieves it.

Do this lesson first: coin change

Example input

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

Expected output

57 scalar multiplications, grouped as (A(B(C(DE))))

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, into one, exactly as on matrix-chain-multiplication: matrix m is dims[m] × dims[m + 1], lettered A, B, C, ... from 0, and the answer sits at dp[0][n - 1]. Printing a grouping needs one more fact per cell, which k won it, because the grouping cannot be read off the values alone without redoing the arithmetic: a cell's value says how cheap its chain can be, its winning k says where that chain's outermost brackets go. That k is a byproduct of the min the cell already takes, so it is remembered alongside the value, not computed by a second recurrence.

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], with split[i][j] = the first k that reaches it; then group(i, i) is the letter of matrix i, and group(i, j) = "(" + group(i, split[i][j]) + group(split[i][j] + 1, j) + ")"

However the chain i..j is bracketed, it ends with ONE last multiplication, joining the product of i..k with the product of k + 1..j, and that multiplication costs dims[i] × dims[k + 1] × dims[j + 1] whatever happened inside the two sides, so each side should be as cheap as it can be on its own. Try every k and keep the cheapest: dp[i][k] + dp[k + 1][j] + dims[i] × dims[k + 1] × dims[j + 1]. The k that wins is the reconstruction's whole content, because the last multiplication of a chain is its outermost pair of brackets: the left side goes inside on the left, the right side on the right, and each side is bracketed by its own winning k. 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, and a single matrix prints as its own letter. Every longer chain reads, for each split after matrix k, its left side dp[i][k] in its own row and its right side dp[k + 1][j] in its own column, both strictly shorter, so the table fills by length, shortest first, along the diagonals to the top-right corner. The walk runs the other way, after the table is full: from the corner down, and it only ever visits chains some winning split produced.

The table is O(n³) time and O(n²) space, as on matrix-chain-multiplication; at 5 matrices it is 15 cells, 5 bases and 10 computes, reading 40 values for 20 split points. The walk is what this page adds, and it is cheap. Start at dp[0][n - 1], take its winning split, and recurse into both sides until each side is a single matrix. Every visit either prints a letter or splits a chain in two, so a chain of n matrices is visited 2n - 1 times, 9 at 5 matrices: O(n) on top of the table. On the page the fill is animated cell by cell, each compare flash marking the split that wins, which is the split the walk follows if it reaches that cell; the walk itself is the closing sentence, stated from the splits the table actually chose.

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.

Rows ↓
Cols →

A 3×5

B 5×2

C 2×4

D 4×6

E 6×1

A 3×5

114

B 5×2

108

C 2×4

D 4×6

E 6×1

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

printing-matrix-chain-multiplication.ts

1function printMatrixChain(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 const split = Array.from({ length: n }, () => new Array(n).fill(-1));
5 for (let len = 2; len <= n; len++) {
6 for (let i = 0; i + len - 1 < n; i++) {
7 const j = i + len - 1;
8 let best = Infinity;
9 for (let k = i; k < j; k++) {
10 const cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1];
11 if (cost < best) { best = cost; split[i][j] = k; } // first cheapest k wins
12 }
13 dp[i][j] = best;
14 }
15 }
16 const group = (i, j) => i === j
17 ? String.fromCharCode(65 + i) // A, B, C, ...
18 : "(" + group(i, split[i][j]) + group(split[i][j] + 1, j) + ")";
19 return { cost: dp[0][n - 1], grouping: group(0, n - 1) };
20}

Base caseComputedBeing readAnswer

The code, the trap, the variations

printing-matrix-chain-multiplication.ts

1function printMatrixChain(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 const split = Array.from({ length: n }, () => new Array(n).fill(-1));
5 for (let len = 2; len <= n; len++) {
6 for (let i = 0; i + len - 1 < n; i++) {
7 const j = i + len - 1;
8 let best = Infinity;
9 for (let k = i; k < j; k++) {
10 const cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1];
11 if (cost < best) { best = cost; split[i][j] = k; } // first cheapest k wins
12 }
13 dp[i][j] = best;
14 }
15 }
16 const group = (i, j) => i === j
17 ? String.fromCharCode(65 + i) // A, B, C, ...
18 : "(" + group(i, split[i][j]) + group(split[i][j] + 1, j) + ")";
19 return { cost: dp[0][n - 1], grouping: group(0, n - 1) };
20}

Where people go wrong

Choosing each bracket by the cost of its own final multiplication, top down. It sounds like the table's idea run backwards: for ABCDE the multiplication that joins the two sides is cheapest after B (6, against 15, 12 and 18), so split there and recurse. That prints ((AB)(C(DE))), which costs 30 + 32 + 6 = 68, not 57: the cheap join hides the 30 spent building AB, and only the full sum, both sides included, sees it. The other slip is in the walk itself: recovering each split from the finished table as the k with the smallest dp[i][k] + dp[k + 1][j], leaving out the join. On this page that happens to print the right grouping at 5 matrices, but at 4 it prints (((AB)C)D), which costs 126, instead of ((AB)(CD)) for 114, and at 8 its grouping costs 183 against 96. Record the k the min actually chose, or put the join back in when you look for it.

Drop the split table and recover each k during the walk.
At each chain the walk visits, scan k for one where dp[i][k] + dp[k + 1][j] + dims[i] × dims[k + 1] × dims[j + 1] equals dp[i][j]. The table and its recurrence are unchanged and the second n by n array goes; the walk now costs up to n - 1 checks per chain it visits, O(n²) in all, still below the O(n³) fill. The join has to be in that check; the pitfall shows what leaving it out prints.
Print every cheapest grouping, not just one.
Keep every k that ties for the minimum at each cell instead of the first, and let the walk branch at a tie, combining every grouping of the left side with every grouping of the right. The table does not change; the output can grow quickly when ties are common. On this page's dimensions there is exactly one cheapest grouping at every slider size, so the list would hold one entry each time.
Print the multiplications in the order to run them, not brackets.
The same walk, emitting a multiplication after both sides of a split are done (post-order) instead of wrapping them in brackets. A chain of n matrices always takes n - 1 multiplications whatever the grouping; at 5 matrices the order is D times E, then C times that, then B, then A, costing 24, 8, 10 and 15, which add up to 57.

Matrix Chain Multiplication Maximum sum rectangle