Matrix chain multiplication
Multiplying matrices is associative, so the answer does not depend on the order — but the cost does, often by orders of magnitude. The table holds the cheapest cost of multiplying each subchain. To fill a cell you try every place the subchain could be split in two, add the cost of the two halves and the cost of the single multiplication that joins them, and keep the smallest. Both halves are shorter than the whole, so every cell a split needs is on an earlier diagonal.
Its recurrence
M(i, j) = min over k in [i, j) of M(i, k) + M(k+1, j) + pᵢ₋₁ · pₖ · pⱼ
When it is the right choice
Any time an associative operation has a cost that depends on where the brackets go: matrix products in graphics and machine learning, join ordering in a query planner, and parsing problems with the same shape. It is also the standard example of interval dynamic programming, which is the family this fill order belongs to — the same shape solves optimal binary search trees and polygon triangulation.
How it works
- Number the matrices 1 to n; the dimension list has one more entry than there are matrices.
- Fill the diagonal with zeroes: a single matrix costs nothing to multiply.
- Work outwards one diagonal at a time, shortest subchains first.
- For each subchain, try every split point inside it.
- Add the two halves already in the table plus the cost of the final multiplication, and keep the smallest.
- Walk back from the whole chain, following the remembered splits, to read off where the brackets go.
Worth noticing
- The fill order is the lesson. This is the only page here that does not fill row by row or left to right, and the reason is visible: every cell needs two cells on shorter diagonals, so no row can be completed before the diagonals beneath it are.
- Half the table is not part of the problem at all — a subchain from i to j only makes sense when i is at or before j — and the unused half is drawn as unused rather than as empty.
- The traceback is a tree, not a path. Each split names two smaller subchains and each of those may split again, so the walk back produces a bracketing rather than a sequence, and the cells it visits are a shape rather than a line.
Cost
- Best
- O(n³)
- Average
- O(n³)
- Worst
- O(n³)
- Extra space
- O(n²)
- Table
- two dimensions
- Accepts
- 4 to 9 dimensions, each from 1 to 99
The limits are pedagogical rather than technical: this tool keeps the whole table in every recorded step, so the shape of the table sets the size of the trace directly, and a run has to stay short enough to sit and watch. An input that would take more than three thousand steps on this algorithm is refused before a single step is generated, from a formula in the input sizes rather than by running it and finding out.
An unfilled cell is drawn differently from a cell holding a zero — no fill, a dashed outline, and no number at all — because early in a run that difference is most of the picture.