A dynamic program is three things: a table, a recurrence, and an order to fill it in. The recurrence is the part nobody gets wrong. Fill the matrix-chain table by interval length and it reports 15 125 multiplications, which every one of the 42 bracketings confirms. Fill the same recurrence row by row and it reports 9 000. Nothing crashes, nothing is empty, and the smaller number is the wrong one.
Core ideas
The hard idea is that reading a cell too early is not an error condition. It is a silent substitution of zero, and the table finishes looking exactly like a table that worked.
The cell for the interval from i to j asks, for each split point k inside it, what the two halves cost and what joining them costs, and keeps the best. Both halves are strictly shorter intervals. So every cell depends on cells nearer the diagonal, and an order that reaches a cell before both of its halves exist is reading something that has not been computed.
The table filler returns nothing for a cell that has not been written yet, and adding nothing to a number in this language gives the number. So a recurrence that reads too early does not raise, does not print a blank and does not leave a gap. It computes a smaller total from a missing half and stores it, and every cell that later reads that cell inherits the error without noticing.
Row-major reports 9 000 against the correct 15 125. A reader checking the arithmetic of one cell would find it consistent, and a reader who expected the optimum to be small would be encouraged. The only cheap defence is a second route: the lab enumerates all 42 bracketings and reports the smallest, and it is 15 125. The order that is wrong is the one that disagrees with the enumeration.
The material
What the chain problem asks, why the order is forced, what happens when it is not respected, and the count that catches it.
A chain of n matrices is given by n + 1 dimensions: p(0), p(1), …, p(n), where matrix i is p(i−1) by p(i). Multiplying a p by q matrix with a q by r matrix costs p·q·r scalar multiplications. The problem is to choose the bracketing — not the order of the matrices, which is fixed — that minimises the total.
Seven numbers describe six matrices. The lab loads 30 35 15 5 10 20 25, so the first matrix is 30 by 35, the second is 35 by 15, and so on. The product is the same matrix whatever the bracketing, because matrix multiplication is associative; only the cost of computing it changes, and on this chain it changes by a factor of nearly four between the best and worst bracketings.
Let cost(i, j) be the fewest scalar multiplications needed to multiply matrices i through j, with cost(i, i) = 0. Then for i < j, cost(i, j) is the minimum over split points k with i ≤ k < j of cost(i, k) + cost(k+1, j) + p(i)·p(k+1)·p(j+1).
Any bracketing of matrices i through j has a last multiplication, which joins a bracketed product of i through k with a bracketed product of k+1 through j for some k. Those two products have dimensions determined by i, k and j alone, so the cost of the join is p(i)·p(k+1)·p(j+1) whatever the two halves did internally.
If either half were bracketed more cheaply, substituting it in would bracket the whole more cheaply, so each half of an optimal bracketing is itself optimal — optimal substructure, discharged. Taking the minimum over the j − i possible values of k therefore gives the optimum, and the recurrence is exact.
□
cost(i, j) reads cost(i, k) and cost(k+1, j), and both of those cover shorter intervals than i to j. So the cells have to be filled in increasing order of j − i: all the zero-length intervals, then all the length-one intervals, and so on. That is a diagonal-by-diagonal sweep, and it fills 21 cells of the 36 in a six-by-six table, because only the upper triangle means anything.
The order a reader writes, because it is the order every other table in this course is filled in, is row by row. Row-major visits (0,0), (0,1), (0,2) and so on across the whole first row before it has filled a single cell of the second. But (0,2) needs (1,2), which is in the second row. It reads it anyway.
Correct: cost(0,2) = min(cost(0,0) + cost(1,2) + 30·35·5, cost(0,1) + cost(2,2) + 30·15·5) = min(0 + 2625 + 5250, 15750 + 0 + 2250) = 7875. Row-major: when it reaches (0,2), the cell (1,2) has not been written, so the first option evaluates to 0 + 0 + 5250 = 5250, which is smaller than 18 000, and 5250 is stored. The table now contains a number that no bracketing of those three matrices achieves.
The damage propagates. Every later cell that reads (0,2) reads 5250, and the final answer in the corner comes out 9 000. Thirty-five reads over the whole fill land on cells that have not been written, and the lab counts them and paints them red. Fill by interval length and that count is zero.
Row-major writes all 36 cells; by-length writes 21. So the wrong order is not a shortcut — it does more work, produces a fuller-looking table, and reports a number two-fifths below the truth. Both orders make the same 70 reads, because the recurrence is the same recurrence; what differs is whether the read finds anything.
The measured counts here are 15 125 and 9 000 on one chain of six matrices, and 42 bracketings agreeing with the first of them. The proved bound is a different statement: the table has Θ(n²) meaningful cells and each takes O(n) work, so filling it is Θ(n³), against Catalan(n−1) bracketings for the enumeration — 42 at six matrices, 132 at seven, 1 430 at nine. The enumeration is the only reason we know 15 125 is right, and it is also the thing that stops being runnable first.
Interactive
By interval length against row by row, both against every bracketing
Method
The order is derived from the recurrence's reads, not from how the table looks on the page.
Not the shape of the dependency — the list. For the chain it is (i, k) and (k+1, j) for every split k, which is two cells per split and j − i splits. The lab records that list from the reads the recurrence actually performed, so it can be compared with yours.
Sort the cells by whatever quantity the dependencies decrease: interval length here, remaining amount in the coin table, prefix length in the string tables. That quantity is the thing the recurrence recurses on, and the order is always increasing in it.
A wrong order produces a complete table and a plausible number, so the way to see it is to run it. The lab keeps both on screen; away from the lab, fill the table twice and compare the corners.
Enumerate every bracketing while the chain is short enough — 42 at six matrices, 132 at seven, 429 at eight, which is the cap. If the two disagree, the table is wrong and the order is the first thing to suspect.
Zero is the only acceptable number, and it is a check you can make once rather than a property you have to argue about. Any positive count means the order is wrong even if the answer happened to come out right.
Rows and columns are matrices one to six; the cell in row i and column j is the cost of multiplying matrices i through j. Only the upper triangle carries meaning. The by-length fill leaves the lower triangle untouched; the row-major fill writes zeros into it and reads them.
Compare the two tables cell by cell and the divergence starts at (A1, A3): 7875 against 5250. Everything to its left agrees, because those cells read only the diagonal, which both orders have already written. Everything to its right is contaminated, and the corner is 9 000 instead of 15 125.
The second table's lower triangle is not empty, it is zeros, and those zeros are what the first row read. That is the mechanism in one sentence: the recurrence asked for a cell, the table had no value for it, and the arithmetic treated the absence as nothing rather than refusing. Any new recurrence written against this table filler has to know that, because a recurrence that reads too early will not tell you.
For a faded rehearsal, switch the dimensions to 10 10 10 10 10 before you run it. The supplied first move: every matrix is 10 by 10, so every multiplication costs 1 000 and the total is three multiplications whatever the bracketing. Predict what by-length reports, predict what row-major reports, and check both — the answers are 3 000 and 1 000, and the enumeration of all five bracketings says the first.
You should be able to list the cells one cell reads, order the table by the quantity the recurrence decreases, run the order you rejected, and check the corner against an enumeration that has no table in it.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.