A table returns a number. A bracketing is an object, and getting the object back means following the split point each cell recorded. Those are two different claims and they are checked separately here: the number against every one of the 132 bracketings of seven matrices, and the tree against the dimensions it was supposedly built from.
Core ideas
The hard idea is that a reconstruction is a separate claim from the value, and it fails in a way the value cannot: it can return a plausible object that costs something else entirely.
Each cell records not only its value but which k attained the minimum. Reading the answer back means starting at the whole interval, taking its split, and recursing on the two halves — which produces a binary tree over the matrices, and that tree printed with brackets is the bracketing. The value came from a minimum; the object comes from a pointer, and they can disagree.
Given the tree and the dimensions, the cost can be worked out from scratch: each internal node costs the product of three dimensions determined by the span of its two children, and the total is the sum over nodes. Nothing in that calculation looks at the table. When the table says 2052 and the re-costed tree says 2052, two independent computations have agreed.
Listing every bracketing needs no recurrence and no order, so it cannot share a mistake with the table. It is also Catalan(n−1), which is 132 at seven matrices, 429 at eight, and past a hundred million by nineteen. The lab refuses above eight. That is the shape of the whole subject: the check you trust most is the one you can least afford.
The material
Where Catalan numbers come from here, how the reconstruction walks, what re-costing proves, and what the two counts say about each other.
A bracketing of matrices 1 through n is a binary tree whose leaves are the matrices in order and whose internal nodes are multiplications. Its cost is the sum, over internal nodes, of p·q·r where the left child spans dimensions p by q and the right child q by r.
The number of bracketings of n matrices is the Catalan number C(n−1), where C(0) = 1 and C(m) = sum over i of C(i)·C(m−1−i) for i from 0 to m−1.
A bracketing of n ≥ 2 matrices has a last multiplication, splitting the chain after matrix k for some k from 1 to n−1. The left part is a bracketing of k matrices and the right part a bracketing of n−k, and the two are chosen independently, so the count for n is the sum over k of the count for k times the count for n−k.
Writing c(n) for the count, that is c(n) = sum over k of c(k)·c(n−k) with c(1) = 1, which is the Catalan recurrence shifted by one. Hence c(n) = C(n−1), giving 5 at four matrices, 42 at six and 132 at seven — and the lab's enumeration returns exactly those counts, because it is the same recursion with the trees kept instead of counted.
□
The split in that proof is the same split the recurrence minimises over. That is not a coincidence: the recurrence is the enumeration with the sub-answers reused instead of rebuilt, which is what dynamic programming is. The table's Θ(n³) and the enumeration's Catalan(n−1) are two costs for the same search, differing only in whether the sub-results are stored.
The reconstruction starts at the cell covering the whole chain and reads its recorded split k. That gives two intervals, i to k and k+1 to j, each of which has its own recorded split, and the recursion bottoms out at single matrices. On the lab's seven-matrix chain the result is ((A1A2)(((A3A4)(A5A6))A7)), which is a bracketing of seven matrices in the given order, as it has to be.
The table reports 2052 after filling 28 cells. The enumeration walks all 132 bracketings with no table at all and reports a best of 2052 and a worst of 14 060. The reconstruction returns the tree above, and re-costing that tree from 5 10 3 12 5 50 6 4 gives 2052. Three numbers, three routes, one answer — and the third route is the only one that says anything about the tree.
Why insist on the third route? Because a reconstruction that follows the wrong pointer returns a bracketing, not an error. It is still a binary tree over the matrices in order; it is still printable; it still looks like an answer. The only cheap way to catch it is to cost it independently and compare with the number the table reported, which is what the panel's re-cost row does.
On this chain the table fills 28 cells and the enumeration walks 132 bracketings, so the table is ahead by a factor of about five. At four matrices the table fills 10 cells against 5 bracketings and the table is behind. The crossing is early here, which is why matrix chain is the friendly case, and the next course on this path has a problem where the crossing does not arrive until ten items.
Both numbers on the panel are measured on the chain on screen. The proved statements are Θ(n³) against Catalan(n−1), and Catalan grows like 4^n over n to the three halves, so the ratio widens without bound. Neither of those growth claims is established by the two counts, and the counts are what tell you that on four matrices the asymptotically better method is the slower one.
One more thing the enumeration buys: the worst bracketing. On this chain it costs 14 060 against the optimum's 2052, a factor of about 6.9. The table cannot tell you that, because it only ever keeps minima, and a reader who wants to know what the optimisation is worth has to ask the enumeration while the enumeration is still affordable.
Interactive
By interval length against row by row, both against every bracketing
Method
The value and the object are different claims, and the second one needs its own check.
When a cell takes a minimum, store which option attained it. Without that the table answers what the optimum costs and cannot answer what it is, and recovering the choice afterwards means recomputing the minimum.
Start at the cell covering everything, follow its recorded choice into subproblems, and stop at the base cases. For the chain that walk is a binary tree; for a knapsack it is a path; the shape of the walk is the shape of the answer.
Compute what the returned object costs, using only the problem's data and not the table. This is the check that catches a reconstruction that followed a stale or wrong pointer, because such a reconstruction still returns a well-formed object.
Every bracketing at six, seven and eight matrices is 42, 132 and 429, and the lab refuses above eight. Use the enumeration to establish the table on small instances, then rely on the table — and write down the size at which you stopped being able to check.
The dimensions are 5 10 3 12 5 50 6 4, so the matrices are 5 by 10, 10 by 3, 3 by 12, 12 by 5, 5 by 50, 50 by 6 and 6 by 4. The table is 7 by 7 and only the upper triangle carries meaning.
Every line of the re-costing uses only the dimensions and the shape of the tree. No cell of the table appears in it. That is what makes the agreement worth something: if the reconstruction had followed a wrong split the tree would still be a tree, the six products would still be computable, and the total would have come out as something other than 2052.
The gap between 2052 and 14 060 is what the optimisation is worth on this chain, and it is knowable only by enumeration. Switch the dimensions to 10 100 5 50 and the same gap is 7 500 against 75 000, exactly ten times, on four matrices and two bracketings. Switch to 10 10 10 10 10 and the gap vanishes: every bracketing costs 3 000, so the optimum is unique in value and not in shape, and the split the table records is one arbitrary choice among five.
For a faded rehearsal, predict the number of bracketings for eight matrices before you change the dimensions. The supplied first move: the counts so far are 1, 2, 5, 14, 42, 132 for one through seven matrices, and each is the sum of products of earlier pairs. Work out the next one, then add a dimension and read the panel — and note that one more matrix after that is refused.
You should be able to store the choice a cell made, walk it back into an object, re-cost that object from the problem's data alone, and say at what size the exhaustive check you were relying on stops running.
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.