DP problems — matrix chain multiplication: Visual walkthrough

We will use one running chain the whole way: $A_{1} (30 \times 35), A_{2} (35 \times 15), A_{3} (15 \times 5), A_{4} (5 \times 10)$ so the dimension array (the list of numbers that describes all the shapes) is $p = [p_{0}, p_{1}, p_{2}, p_{3}, p_{4}] = [30, 35, 15, 5, 10] .$

Step 1 — What a matrix "shape" is, and what one multiplication costs

WHAT. A matrix is just a grid of numbers. Its shape is written rows × columns. Matrix $A_{2}$ is $35 \times 15$ : 35 rows, 15 columns. In the dimension array, $A_{i}$ has shape $p_{i - 1} \times p_{i}$ — it borrows the number on its left ( $p_{i - 1}$ ) for rows and the number on its right ( $p_{i}$ ) for columns.

WHY only shapes. To count effort we never need the actual numbers inside — the effort depends only on how big the grids are. So we throw away the contents and keep the shape list $p$ .

PICTURE. To multiply an $a \times b$ grid by a $b \times c$ grid, the two inner numbers must match (both $b$ ). You produce an $a \times c$ result, and each of its $a \cdot c$ cells is a sum of $b$ products.

Figure — DP problems — matrix chain multiplication

Step 2 — Two orders, wildly different bills

WHAT. Take just the first three matrices and glue them two-at-a-time. Two possible orders exist. The final grid is identical (matrix multiplication is associative), but the running total of scalar multiplications is not.

WHY it matters. If both orders cost the same we would have no problem to solve. They don't — sometimes by a factor of 10 or more — so choosing the order is worth real work.

PICTURE. Watch the intermediate grid each order builds. A fat intermediate grid is what makes an order expensive.

Using $p = [10, 100, 5, 50]$ (a sharper illustration):

$(A_{1} A_{2}) A_{3} : 5000 10 \cdot 100 \cdot 5 + 2500 10 \cdot 5 \cdot 50 = 7500$ $A_{1} (A_{2} A_{3}) : 25000 100 \cdot 5 \cdot 50 + 50000 10 \cdot 100 \cdot 50 = 75000$

Step 3 — The one idea: look at the LAST glue

WHAT. Forget how the whole product is built. Ask only: which multiplication happens last? Whatever the parenthesization, there is exactly one outermost multiply, and it joins a left block to a right block.

WHY this question. It cuts a hard problem into two smaller, independent problems. If the last glue sits after matrix $A_{k}$ , then:

everything to the left, $A_{i} \dots A_{k}$ , has already collapsed into one grid,
everything to the right, $A_{k + 1} \dots A_{j}$ , has already collapsed into one grid,
and their internal costs don't affect each other. This is optimal substructure.

PICTURE. The split point $k$ is a single cut in the chain. The two halves are their own miniature MCM problems.

Step 4 — What the last glue costs

WHAT. After the two halves collapse, we know their shapes exactly from $p$ :

Left block $A_{i} \dots A_{k}$ produces a $p_{i - 1} \times p_{k}$ grid.
Right block $A_{k + 1} \dots A_{j}$ produces a $p_{k} \times p_{j}$ grid.

WHY these shapes. The left block starts at $A_{i}$ (rows $p_{i - 1}$ ) and ends at $A_{k}$ (columns $p_{k}$ ). The right block starts at $A_{k + 1}$ (rows $p_{k}$ ) and ends at $A_{j}$ (columns $p_{j}$ ). The two inner numbers are both $p_{k}$ — they match automatically, which is why consecutive blocks can always be glued.

PICTURE. Three boundary numbers survive: $p_{i - 1}$ , $p_{k}$ , $p_{j}$ . By Step 1's rule the final glue costs their product.

Step 5 — Assembling the recurrence

WHAT. Name the thing we want: let $m [i] [j]$ be the minimum number of scalar multiplications to fully collapse $A_{i} \dots A_{j}$ . The total cost for a chosen split $k$ is: cost of the left half + cost of the right half + the final glue.

WHY a min over $k$ . We do not know the best cut in advance (Step 2 proved greedy guessing fails). So we try every legal cut $k$ and keep the cheapest — that is the only honest choice.

PICTURE. Each candidate $k$ is one branch. We evaluate them all and pick the shortest bar.

Step 6 — The degenerate & edge cases (never leave a gap)

WHAT. Every corner the reader could hit:

One matrix ( $i = j$ ): the min has no valid $k$ (the range $i \leq k < j$ is empty). We must not call min on an empty set → this is precisely why the base case $m [i] [i] = 0$ exists as a separate branch.
Two matrices ( $j = i + 1$ ): exactly one legal $k = i$ . No real choice, cost is just $p_{i - 1} p_{i} p_{i + 1}$ — matches Step 1's single-multiply cost, as it should.
A dimension equal to 1 (e.g. a row or column vector): the formula still works; a $1$ in the product just makes that glue cheap. Nothing special-cased.
Empty chain ( $n = 0$ , array length 1): no matrices, cost $0$ — guard before the loops.

WHY show these. A recurrence that crashes on the smallest input is not finished. The base case is not decoration; it is the floor the whole recursion stands on.

PICTURE. The recursion tree bottoms out only when every leaf is a single matrix (cost 0).

Step 7 — Why fill by chain LENGTH, not by rows

WHAT. To compute $m [i] [j]$ we need $m [i] [k]$ and $m [k + 1] [j]$ — both are shorter chains. So we must have all short chains before any long one.

WHY not row-by-row. Reading a table left-to-right, top-to-bottom would ask for $m [1] [4]$ (length 4) while $m [2] [4]$ (length 3) is still blank. Fill by increasing length $L = j - i + 1$ instead: $L = 1$ (the zeros), then $L = 2$ , up to $L = n$ .

PICTURE. The DP table filling as diagonals sweeping outward from the main diagonal.

Working our chain $p = [30, 35, 15, 5, 10]$ :

$m [1] [2] = 15750, m [2] [3] = 2625, m [3] [4] = 750 (L = 2)$ $m [1] [3] = 7875 (k = 1), m [2] [4] = 4375 (k = 3) (L = 3)$ $m [1] [4] = min {14875, 21000, 9375} = 9375 (k = 3) (L = 4)$

Recall Where does 9375 come from?

Best split of the full chain is $k = 3$ ::: $((A_{1} A_{2} A_{3}) A_{4})$ , and inside $s [1] [3] = 1$ gives $(A_{1} (A_{2} A_{3}))$ , so the answer is $((A_{1} (A_{2} A_{3})) A_{4})$ at cost 9375.

The one-picture summary

Everything above compressed into a single frame: the chain, one last cut at $k$ , two collapsed halves, three surviving boundary numbers feeding the glue cost, and the min over all cuts feeding the DP table filled by length.

Recall Feynman retelling — the whole walkthrough in plain words

You have a row of paper sheets to stack-glue, two at a time. Gluing an $a \times b$ sheet onto a $b \times c$ sheet costs $a \cdot b \cdot c$ effort (Step 1). The final sheet looks the same no matter the gluing order, but the effort can differ 10× because fat middle sheets are expensive (Step 2). The trick: think about the very last glue — it always splits the row into a left piece and a right piece that were built independently (Step 3). Once split, the shapes of the two pieces are fixed by the boundary numbers, so the last glue costs $p_{i - 1} p_{k} p_{j}$ (Step 4). We don't know the best place to cut, so we try every cut and keep the cheapest — that's the min over $k$ (Step 5). A single sheet costs nothing, which is the floor of the whole idea (Step 6). And because a long piece is built from shorter ones, we solve short pieces first, sweeping the table by length (Step 7). That's the entire algorithm — one honest "try all last cuts" repeated cleverly.

Connections

Dynamic Programming — the optimal-substructure engine behind Step 5
Catalan Numbers — how many parenthesizations exist ( $C_{n - 1}$ ), i.e. why brute force loses
Optimal Binary Search Tree — same "try every split" interval-DP shape
Burst Balloons — interval DP where you instead fix the last balloon
Memoization vs Tabulation — top-down vs the length-sweep here
Time Complexity Analysis — the $O (n^{3})$ from loops over $L, i, k$