DP problems — matrix chain multiplication: Worked examples

Before we start, recall the objects we keep re-using — including one, the split table, that we lean on so heavily it deserves its own definition.

Definition The tools we lean on (with the split table made explicit)

Dimension array $p = [p_{0}, p_{1}, \dots, p_{n}]$ . Matrix $A_{i}$ is $== p_{i - 1} \times p_{i} ==$ . So $n$ matrices need $n + 1$ numbers. An array of length $1$ (just $[p_{0}]$ ) means $n = 0$ — zero matrices.
Combine cost of gluing an $a \times b$ block to a $b \times c$ block is $== a \cdot b \cdot c ==$ scalar multiplications — one multiply per output entry ( $a \cdot c$ of them) times the shared length $b$ .
Cost table $m [i] [j]$ = minimum multiplications to build $A_{i} \dots A_{j}$ . Recurrence: $m [i] [j] = min_{i \leq k < j} (m [i] [k] + m [k + 1] [j] + p_{i - 1} p_{k} p_{j})$ , with $m [i] [i] = 0$ .
Split table $s [i] [j]$ = the winning cut point $k$ for interval $[i, j]$ . Whenever the min above is achieved at some $k$ , we record $s [i] [j] = k$ . This second table stores nothing about cost — only where the cheapest last multiplication happened — so that later we can rebuild the actual brackets. Cost tells you how much; the split table tells you how.

Because two examples below fill these tables in code-order, here is the exact loop structure we follow — the variable names ( $L$ , $i$ , $j$ , $k$ ) are used verbatim later, so meet them now:

n = len(p) - 1                     # number of matrices
m[i][i] = 0 for all i              # base case
for L in 2..n:                     # L = chain length, OUTERMOST
    for i in 1..n-L+1:             # left end of the interval
        j = i + L - 1              # right end (so length is exactly L)
        m[i][j] = +infinity
        for k in i..j-1:           # try every last-cut position
            cost = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
            if cost < m[i][j]:
                m[i][j] = cost
                s[i][j] = k        # <-- remember the winning split

The scenario matrix

Every MCM input falls into one of these case classes. The last column names the worked example that covers it, so you can see the whole space is filled — starting from the truly empty chain.

Case class	What makes it special	Covered by
Empty chain: $n = 0$	array length $1$ , no matrices at all	Example 0
Degenerate: $n = 1$	one matrix, nothing to multiply	Example 1
Minimal branch: $n = 2$	exactly one split, no choice	Example 2
First real choice: $n = 3$	two splits compete	Example 3
All-square chain	every $p_{i}$ equal → symmetry, ties	Example 4
Skinny middle matrix	one tiny dimension changes the answer	Example 5
Tie between split points	two $k$ give equal cost — which to store?	Example 6
Scalar output ( $p_{0} = p_{n} = 1$ )	chain collapses to a $1 \times 1$ number	Example 7
Word problem (real world)	translate a story into a $p$ array	Example 8
Exam twist: count vs recover	asked for the parenthesization, not just cost	Example 9

We work them in order. Each example first asks you to Forecast the answer before you compute — that guess is where the learning happens.

Example 0 — Empty chain ( $n = 0$ )

Forecast: if there is nothing to multiply, is the cost $0$ , undefined, or an error? Guess before reading.

Compute $n$ . Why this step? Every MCM run begins by turning the array into a matrix count. Here $n = 0$ .
Check whether any loop body executes. Why this step? The outer loop runs for L in 2..n, i.e. 2..0, which is empty — zero iterations. No interval $[i] [j]$ with $i < j$ exists.
Read off the answer. Why this step? There is no $m [1] [n]$ to return (there is no matrix $A_{1}$ ). The total cost of multiplying nothing is $0$ by convention, exactly as the empty sum is $0$ .

$cost = 0$

Verify: An empty product needs no work, so $0$ is the only sensible value; the loops never fire, so nothing breaks. This is the boundary you must handle in code (guard if n <= 1: return 0) — units are multiplications, and we performed none. ✓

Example 1 — Degenerate: a single matrix ( $n = 1$ )

Forecast: ...how much work is there if nothing gets multiplied? Guess before reading.

Count the matrices. Why this step? The array has length $2$ , and $n = len (p) - 1 = 1$ . One matrix.
Apply the base case. Why this step? The recurrence's first branch says $m [i] [i] = 0$ . Here $i = j = 1$ , so we hit the base case directly — there is no split point $k$ with $i \leq k < j$ because $j = i$ .

$m [1] [1] = 0$

Verify: A single matrix is already "multiplied". No scalar multiplications happen, so $0$ is correct — units are multiplications, and we did none. ✓

Example 2 — Minimal branch: exactly one split ( $n = 2$ )

Forecast: with only two matrices there is nothing to choose — but what number comes out?

List the valid splits. Why this step? $k$ ranges over $i \leq k < j$ , i.e. $1 \leq k < 2$ , so only $k = 1$ . No minimum to take — one candidate, and so $s [1] [2] = 1$ automatically.
Plug into the combine formula. Why this step? Left block $A_{1}$ is $p_{0} \times p_{1}$ , right block $A_{2}$ is $p_{1} \times p_{2}$ , so combine cost is $p_{0} p_{1} p_{2}$ . Sub-costs $m [1] [1] = m [2] [2] = 0$ .

$m [1] [2] = 0 + 0 + p_{0} p_{1} p_{2} = 10 \cdot 100 \cdot 5 = 5000$

Verify: The output is $10 \times 5$ , so $50$ entries, each summing $100$ products → $50 \times 100 = 5000$ multiplications. Matches. ✓

Example 3 — The first real choice ( $n = 3$ )

This is the parent note's motivating chain — we redo it as a decision between the only two options, $k = 1$ and $k = 2$ . There are exactly two candidate trees, and the figure draws both so you can see which survives.

Forecast: one split puts the big $100$ dimension inside a combine, the other keeps it outside. Which is cheaper — and by how much?

Figure — DP problems — matrix chain multiplication

Figure — two binary trees side by side. Left (teal): the $k = 1$ tree $(A_{1}) (A_{2} A_{3})$ ; its root "×" node multiplies the leaf $A_{1}$ against the sub-tree $A_{2} A_{3}$ , and its total cost is labelled $75000$ . Right (plum): the $k = 2$ tree $(A_{1} A_{2}) (A_{3})$ ; here $A_{1} A_{2}$ is the sub-tree and $A_{3}$ is the lone leaf, total cost $7500$ . The burnt-orange arrow points from the label "cheaper split kept by min" to the plum tree's root — that is the branch the $min$ operator keeps, so $s [1] [3] = 2$ . Read each tree bottom-up: leaves are original matrices, every "×" is one multiplication, and the tree's shape IS the parenthesization.

Enumerate splits. Why this step? $1 \leq k < 3$ gives $k = 1$ and $k = 2$ . These are the only two ways to place the last multiplication (the two trees in the figure).
Split $k = 1$ : $(A_{1}) (A_{2} A_{3})$ . Why this step? Left is $A_{1}$ (cost $0$ ), right is $A_{2} A_{3}$ (cost $m [2] [3] = 100 \cdot 5 \cdot 50 = 25000$ ), combine $= p_{0} p_{1} p_{3} = 10 \cdot 100 \cdot 50 = 50000$ . $0 + 25000 + 50000 = 75000$
Split $k = 2$ : $(A_{1} A_{2}) (A_{3})$ . Why this step? Left is $A_{1} A_{2}$ (cost $m [1] [2] = 10 \cdot 100 \cdot 5 = 5000$ ), right $A_{3}$ (cost $0$ ), combine $= p_{0} p_{2} p_{3} = 10 \cdot 5 \cdot 50 = 2500$ . $5000 + 0 + 2500 = 7500$
Take the min and record the split. Why this step? The recurrence keeps the cheaper candidate, and $s [1] [3]$ remembers which $k$ won. $7500 < 75000$ , so the winner is $k = 2$ .

$m [1] [3] = 7500, s [1] [3] = 2$

Verify: $10 \times$ difference, matching the parent note's headline. In the figure, the plum tree (the one the orange arrow marks) is the survivor — its shape $(A_{1} A_{2}) A_{3}$ is exactly what $s [1] [3] = 2$ encodes. ✓

Example 4 — All-square chain (symmetry & the ties it creates)

Forecast: when every matrix is identical in shape, does the split point matter at all?

Every combine costs the same. Why this step? Each factor $p_{i - 1}, p_{k}, p_{j}$ equals $4$ , so every combine is $4 \cdot 4 \cdot 4 = 64$ , regardless of $k$ .
Every length-2 subchain costs $64$ . Why this step? A length-2 subchain has a single split, so its cost is just one combine $= p_{i - 1} p_{i} p_{i + 1} = 4 \cdot 4 \cdot 4 = 64$ ; this applies to both $m [1] [2]$ and $m [2] [3]$ , giving $m [1] [2] = m [2] [3] = 64$ .
Try both splits. Why this step? Symmetry predicts a tie, but the algorithm still enumerates all $k$ before trusting one.
- $k = 1$ : $m [1] [1] + m [2] [3] + 64 = 0 + 64 + 64 = 128$
- $k = 2$ : $m [1] [2] + m [3] [3] + 64 = 64 + 0 + 64 = 128$
Result. Both give $128$ ; the min is $128$ (first-seen $k = 1$ recorded, so $s [1] [3] = 1$ ).

$m [1] [3] = 128$

Verify: Any parenthesization does exactly two $4 \times 4 \times 4$ multiplies $= 2 \cdot 64 = 128$ . The equal costs are the hallmark of a square chain — no order beats another. ✓

Example 5 — Skinny middle matrix (one tiny dimension rules)

Forecast: the $10$ (dimension $p_{3}$ ) is a bottleneck. Do good splits try to route through it?

We fill by chain length $L$ , exactly as the loop skeleton at the top demands.

Length 2 ( $L = 2$ ):

$m [1] [2] = p_{0} p_{1} p_{2} = 40 \cdot 20 \cdot 30 = 24000$
$m [2] [3] = p_{1} p_{2} p_{3} = 20 \cdot 30 \cdot 10 = 6000$
$m [3] [4] = p_{2} p_{3} p_{4} = 30 \cdot 10 \cdot 30 = 9000$

Length 3 ( $L = 3$ ): Why now? Each needs two length- $\leq 2$ answers, which we just computed. 4. $m [1] [3] = min {k = 1 : 0 + 6000 + p_{0} p_{1} p_{3} = 6000 + 40 \cdot 20 \cdot 10 = 6000 + 8000 = 14000 k = 2 : 24000 + 0 + p_{0} p_{2} p_{3} = 24000 + 40 \cdot 30 \cdot 10 = 24000 + 12000 = 36000 = 14000 (s [1] [3] = 1)$ 5. $m [2] [4] = min {k = 2 : 0 + 9000 + p_{1} p_{2} p_{4} = 9000 + 20 \cdot 30 \cdot 30 = 9000 + 18000 = 27000 k = 3 : 6000 + 0 + p_{1} p_{3} p_{4} = 6000 + 20 \cdot 10 \cdot 30 = 6000 + 6000 = 12000 = 12000 (s [2] [4] = 3)$

Length 4 ( $L = 4$ , the answer): Why last? It depends on all shorter chains. 6. $m [1] [4] = min ⎩ ⎨ ⎧ k = 1 : 0 + 12000 + p_{0} p_{1} p_{4} = 12000 + 40 \cdot 20 \cdot 30 = 12000 + 24000 = 36000 k = 2 : 24000 + 9000 + p_{0} p_{2} p_{4} = 33000 + 40 \cdot 30 \cdot 30 = 33000 + 36000 = 69000 k = 3 : 14000 + 0 + p_{0} p_{3} p_{4} = 14000 + 40 \cdot 10 \cdot 30 = 14000 + 12000 = 26000$

$m [1] [4] = 26000 (s [1] [4] = 3)$

Verify: The winning split $k = 3$ puts the tiny $p_{3} = 10$ into the outer combine ( $p_{0} p_{3} p_{4} = 40 \cdot 10 \cdot 30$ ), which is the cheapest boundary. The "skinny" dimension acts like a discount coupon — good splits spend it on the biggest combine. ✓

Example 6 — A deliberate tie between split points

Forecast: the shape "goes up-down-up". Will the two splits land on the same cost?

Length-2 costs. $m [1] [2] = p_{0} p_{1} p_{2} = 2 \cdot 3 \cdot 2 = 12$ ; $m [2] [3] = p_{1} p_{2} p_{3} = 3 \cdot 2 \cdot 3 = 18$ .
Split $k = 1$ : $0 + 18 + p_{0} p_{1} p_{3} = 18 + 2 \cdot 3 \cdot 3 = 18 + 18 = 36$ .
Split $k = 2$ : $12 + 0 + p_{0} p_{2} p_{3} = 12 + 2 \cdot 2 \cdot 3 = 12 + 12 = 24$ .
Min. $24 < 36$ , so $m [1] [3] = 24$ at $k = 2$ ( $s [1] [3] = 2$ ).

Now a true tie — change the last dimension so both splits cost the same:

Verify: In the tie variant, mirror symmetry ( $p$ reads $2, 3, 3, 2$ — a palindrome) forces the two trees to cost the same. The algorithm's answer $30$ is optimal regardless of which $k$ it records. ✓

Example 7 — Scalar output ( $p_{0} = p_{n} = 1$ )

Forecast: the outer dimensions are $1$ . Does that make one split almost free?

Length-2 costs. $m [1] [2] = p_{0} p_{1} p_{2} = 1 \cdot 5 \cdot 4 = 20$ ; $m [2] [3] = p_{1} p_{2} p_{3} = 5 \cdot 4 \cdot 1 = 20$ .
Split $k = 1$ : $(A_{1}) (A_{2} A_{3})$ . $0 + 20 + p_{0} p_{1} p_{3} = 20 + 1 \cdot 5 \cdot 1 = 20 + 5 = 25$ .
Split $k = 2$ : $(A_{1} A_{2}) (A_{3})$ . $20 + 0 + p_{0} p_{2} p_{3} = 20 + 1 \cdot 4 \cdot 1 = 20 + 4 = 24$ .
Min. $24 < 25$ , so $m [1] [3] = 24$ at $k = 2$ ( $s [1] [3] = 2$ ).

Verify: Because $p_{0} = p_{3} = 1$ , both outer combines are tiny ( $5$ and $4$ ), so the winner is decided by the inner subchain. The final matrix is genuinely $1 \times 1$ — a plain number — yet the intermediate work still costs $24$ multiplications. Degenerate outer shape ≠ free chain. ✓

Example 8 — Word problem (translate the story)

Forecast: should you fold the three tiny $3 \times 3$ -ish transforms together first, then hit the big $1000$ -row data — or march left to right?

Build the $p$ array. Why this step? MCM only sees dimensions. Chain $A_{1} = D (1000 \times 3)$ , $A_{2} = R (3 \times 3)$ , $A_{3} = S (3 \times 3)$ , $A_{4} = P (3 \times 4)$ . So $p = [1000, 3, 3, 3, 4] .$
Length-2: $m [1] [2] = 1000 \cdot 3 \cdot 3 = 9000$ ; $m [2] [3] = 3 \cdot 3 \cdot 3 = 27$ ; $m [3] [4] = 3 \cdot 3 \cdot 4 = 36$ .
Length-3:
- $m [1] [3] = min {k = 1 : 0 + 27 + 1000 \cdot 3 \cdot 3 = 27 + 9000 = 9027 k = 2 : 9000 + 0 + 1000 \cdot 3 \cdot 3 = 9000 + 9000 = 18000 = 9027 (s [1] [3] = 1)$
- $m [2] [4] = min {k = 2 : 0 + 36 + 3 \cdot 3 \cdot 4 = 36 + 36 = 72 k = 3 : 27 + 0 + 3 \cdot 3 \cdot 4 = 27 + 36 = 63 = 63 (s [2] [4] = 3)$
Length-4: $m [1] [4] = min ⎩ ⎨ ⎧ k = 1 : 0 + 63 + 1000 \cdot 3 \cdot 4 = 63 + 12000 = 12063 k = 2 : 9000 + 36 + 1000 \cdot 3 \cdot 4 = 9036 + 12000 = 21036 k = 3 : 9027 + 0 + 1000 \cdot 3 \cdot 4 = 9027 + 12000 = 21027$ $= 12063 (s [1] [4] = 1) .$

Result: $s [1] [4] = 1$ means the last multiply is $D (R S P)$ : fold the three transforms together first (they are cheap $3 \times 3 \times 3$ -ish), then apply the combined $3 \times 4$ matrix to the huge $1000$ -row data once.

Verify: The naive left-to-right order costs $m [1] [3] + 0 + p_{0} p_{3} p_{4} = 9027 + 12000 = 21027$ (the $k = 3$ path); the optimal $12063$ nearly halves the work — exactly the "combine the small stuff before touching the big matrix" intuition. ✓

Example 9 — Exam twist: recover the parenthesization, not just the cost

Forecast: you know the cost; the trick is turning split indices into nested brackets. Where does the first bracket close?

Recall from the definition box: $s [i] [j]$ is the cut point $k$ where interval $[i, j]$ made its cheapest last multiplication. To rebuild the brackets you read $s$ top-down, biggest interval first.

Start at the whole chain $[1, 4]$ . Why this step? Reconstruction always begins with the outermost interval. $s [1] [4] = 3$ → last cut after $A_{3}$ : $(A_{1} A_{2} A_{3}) (A_{4})$ .
Recurse on the left $[1, 3]$ . Why this step? Its own last cut is $s [1] [3] = 1$ → $(A_{1}) (A_{2} A_{3})$ .
Recurse on $[2, 3]$ . $s [2] [3] = 2$ → $(A_{2}) (A_{3})$ , i.e. just $A_{2} A_{3}$ with the only possible split.
Right side $[4, 4]$ is a single matrix — no bracket.
Assemble inside-out. Why this step? Substitute the pieces: $((A_{1} (A_{2} A_{3})) A_{4}) .$

Verify: This matches the parent note's stated optimal parenthesization exactly, and its cost is $m [1] [4] = 9375$ . The $s$ table is read top-down (biggest interval first), then each sub-interval recursively. ✓

Recall Self-test: name the case class for each

$p = [7]$ (array length $1$ , i.e. zero matrices) vs $p = [7, 7, 7, 7]$ vs $p = [1, 9, 9, 1]$ . $p = [7]$ ::: empty chain, $n = 0$ → cost $0$ , no loop iterations (Example 0). $p = [7, 7, 7, 7]$ ::: all-square chain → every split ties (Example 4 pattern). $p = [1, 9, 9, 1]$ ::: scalar output, palindrome dims → symmetric tie, final result is $1 \times 1$ (Examples 6 & 7 combined). Which loop variable must be outermost so no subchain is unfilled? ::: the chain-length $L$ (grow $L$ from $2$ to $n$ ), never loop by row $i$ . What does $s [i] [j]$ store, and why keep it separate from $m [i] [j]$ ? ::: the winning cut $k$ for interval $[i, j]$ ; $m$ tells how much, $s$ tells how, so we can rebuild the brackets.

Connections

3.7.13 DP problems — matrix chain multiplication (Hinglish) — the parent recurrence these examples exercise
Dynamic Programming — optimal substructure is why per-interval answers combine
Catalan Numbers — how many parenthesizations each of these chains has
Optimal Binary Search Tree — same "try every split, store $s$ " reconstruction
Burst Balloons — interval DP where the last element (not split) is fixed
Memoization vs Tabulation — top-down would compute these same $m [i] [j]$ lazily
Time Complexity Analysis — every example above is $O (n^{3})$ fill work