DP problems — matrix chain multiplication: Exercises

Level 1 — Recognition

L1.1 — Read the dimensions off the array

Given $p = [5, 4, 6, 2, 7]$ , list each matrix $A_{1}, A_{2}, A_{3}, A_{4}$ with its dimensions.

Recall Solution

The rule is " $A_{i}$ uses $p_{i - 1}$ and $p_{i}$ ". Walk the array in overlapping pairs:

$A_{1} = p_{0} \times p_{1} = 5 \times 4$
$A_{2} = p_{1} \times p_{2} = 4 \times 6$
$A_{3} = p_{2} \times p_{3} = 6 \times 2$
$A_{4} = p_{3} \times p_{4} = 2 \times 7$

Why it works: consecutive matrices share a boundary dimension ( $p_{1}$ , $p_{2}$ , $p_{3}$ ), which is exactly why they can be multiplied — the inner dimensions match automatically. Number of matrices $=$ length of $p$ minus one $= 5 - 1 = 4$ .

L1.2 — Cost of a single multiplication

You multiply a $5 \times 4$ matrix by a $4 \times 6$ matrix. How many scalar multiplications?

Recall Solution

Cost $= a \cdot b \cdot c = 5 \cdot 4 \cdot 6 = 120$ . Why: the result is $5 \times 6 = 30$ entries, and each entry is a dot product of length $4$ (the shared middle dimension), so $30 \times 4 = 120$ .

Level 2 — Application

L2.1 — A length-2 chain (only one way)

$p = [10, 20, 30]$ . Compute $m [1] [2]$ .

Recall Solution

Only two matrices, so only one split ( $k = 1$ ): $m [1] [2] = m [1] [1] + m [2] [2] + p_{0} p_{1} p_{2} = 0 + 0 + 10 \cdot 20 \cdot 30 = 6000.$ Why no min needed: with two matrices there is exactly one place to put the parentheses.

L2.2 — A length-3 chain, compare both splits

$p = [10, 100, 5, 50]$ (the motivation example). Compute $m [1] [3]$ by trying both split points, and state the optimal parenthesization.

Recall Solution

Chain $A_{1} A_{2} A_{3}$ , indices $i = 1, j = 3$ . Sub-costs first:

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

Now the two outer splits:

$k = 1$ : $m [1] [1] + m [2] [3] + p_{0} p_{1} p_{3} = 0 + 25000 + 10 \cdot 100 \cdot 50 = 25000 + 50000 = 75000$
$k = 2$ : $m [1] [2] + m [3] [3] + p_{0} p_{2} p_{3} = 5000 + 0 + 10 \cdot 5 \cdot 50 = 5000 + 2500 = 7500$

$m [1] [3] = min (75000, 7500) = 7500$ at $k = 2$ → parenthesization $(A_{1} A_{2}) A_{3}$ .

Why $k = 2$ wins: splitting after $A_{2}$ makes the final combine $10 \cdot 5 \cdot 50$ tiny, because the big dimension $100$ has already been "eaten" inside the cheap $m [1] [2]$ step.

Level 3 — Analysis

L3.1 — Full table for $p = [40, 20, 30, 10, 30]$

Compute $m [1] [4]$ (optimal cost) and the optimal parenthesization. Fill by increasing chain length.

Recall Solution

Matrices: $A_{1} (40 \times 20), A_{2} (20 \times 30), A_{3} (30 \times 10), A_{4} (10 \times 30)$ , $n = 4$ .

Length 2:

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

Length 3:

$m [1] [3]$ :
- $k = 1$ : $0 + 6000 + 40 \cdot 20 \cdot 10 = 6000 + 8000 = 14000$
- $k = 2$ : $24000 + 0 + 40 \cdot 30 \cdot 10 = 24000 + 12000 = 36000$
- min $= 14000$ , $s [1] [3] = 1$
$m [2] [4]$ :
- $k = 2$ : $0 + 9000 + 20 \cdot 30 \cdot 30 = 9000 + 18000 = 27000$
- $k = 3$ : $6000 + 0 + 20 \cdot 10 \cdot 30 = 6000 + 6000 = 12000$
- min $= 12000$ , $s [2] [4] = 3$

Length 4:

$k = 1$ : $m [1] [1] + m [2] [4] + p_{0} p_{1} p_{4} = 0 + 12000 + 40 \cdot 20 \cdot 30 = 12000 + 24000 = 36000$
$k = 2$ : $m [1] [2] + m [3] [4] + p_{0} p_{2} p_{4} = 24000 + 9000 + 40 \cdot 30 \cdot 30 = 33000 + 36000 = 69000$
$k = 3$ : $m [1] [3] + m [4] [4] + p_{0} p_{3} p_{4} = 14000 + 0 + 40 \cdot 10 \cdot 30 = 14000 + 12000 = 26000$

$m [1] [4] = min (36000, 69000, 26000) = 26000$ at $k = 3$ , $s [1] [4] = 3$ .

Reconstruct: $s [1] [4] = 3 \Rightarrow (A_{1} A_{2} A_{3}) (A_{4})$ . Then $s [1] [3] = 1 \Rightarrow (A_{1} (A_{2} A_{3}))$ . Final: $((A_{1} (A_{2} A_{3})) A_{4})$ .

See the table-filling order below — chains grow along the diagonal, never row by row.

Figure — DP problems — matrix chain multiplication

L3.2 — Which cells does $m [1] [4]$ depend on?

Without recomputing, state exactly which table entries must already exist before $m [1] [4]$ can be computed, and explain the diagonal fill order.

Recall Solution

For $m [1] [4]$ the splits $k \in {1, 2, 3}$ require the pairs:

$k = 1$ : $m [1] [1]$ and $m [2] [4]$
$k = 2$ : $m [1] [2]$ and $m [3] [4]$
$k = 3$ : $m [1] [3]$ and $m [4] [4]$

So it needs ${m [1] [1], m [1] [2], m [1] [3], m [2] [4], m [3] [4], m [4] [4]}$ — all of them shorter chains (length $\leq 3$ ). This is why we fill by increasing length $L$ : every cell of length $L$ only ever reaches into cells of length $< L$ , which are already done. See the arrows in the figure below.

Level 4 — Synthesis

L4.1 — Count the parenthesizations (Catalan connection)

How many distinct full parenthesizations does a product of $n = 5$ matrices have? Give the formula and the number.

Recall Solution

The number of parenthesizations of $n$ matrices is the Catalan number $C_{n - 1}$ : $C_{m} = \frac{1}{m + 1} (m 2 m) .$ For $n = 5$ we need $C_{4}$ : $C_{4} = \frac{1}{5} (4 8) = \frac{1}{5} \cdot 70 = 14.$ Why Catalan: picking the outermost split point $k$ recursively creates a left group and a right group, and $C_{n - 1} = \sum C_{left} \cdot C_{right}$ — exactly the Catalan recurrence. See Catalan Numbers. This exponential growth ( $\sim 4^{n} / n^{1.5}$ ) is precisely why brute force is hopeless and DP ( $O (n^{3})$ ) wins.

L4.2 — Memoized top-down version, and why it's the same complexity

Write pseudocode for the top-down memoized MCM and argue it is still $O (n^{3})$ time, $O (n^{2})$ space.

Recall Solution

memo = 2D array filled with -1
def solve(i, j):
    if i == j: return 0
    if memo[i][j] != -1: return memo[i][j]
    best = +infinity
    for k in i..j-1:
        cost = solve(i,k) + solve(k+1,j) + p[i-1]*p[k]*p[j]
        best = min(best, cost)
    memo[i][j] = best
    return best
# answer = solve(1, n)

Why same complexity: there are $O (n^{2})$ distinct $(i, j)$ states (each solved once thanks to memo), and each does an $O (n)$ loop over $k$ → $O (n^{3})$ time. Space is the $O (n^{2})$ memo table (plus $O (n)$ recursion stack). This is the Memoization vs Tabulation equivalence: same states, same transitions, different visiting order. See Time Complexity Analysis.

Level 5 — Mastery

L5.1 — Same paradigm, different combine: Burst Balloons

In Burst Balloons you have balloons with values $v = [3, 1, 5, 8]$ , padded to $[1, 3, 1, 5, 8, 1]$ . Bursting balloon $k$ (last, inside interval $(i, j)$ ) earns $v_{i} \cdot v_{k} \cdot v_{j}$ (adjacent survivors). The recurrence is $d p [i] [j] = max_{i < k < j} (d p [i] [k] + d p [k] [j] + v_{i} v_{k} v_{j}) .$ Explain in one paragraph how this is structurally identical to MCM, and name the one conceptual switch that makes it work.

Recall Solution

Both are interval DP: solve a sub-range by fixing one special element and recursing on the two pieces. In MCM you fix the last multiplication (split at $k$ ), and the two sides are independent because a completed block only exposes its outer dimensions. In Burst Balloons you fix the last balloon burst (not the first!) — because once $k$ is the last to pop inside $(i, j)$ , its neighbours are exactly the survivors $i$ and $j$ , making the two sub-intervals independent. The one conceptual switch: fix the LAST event, not the first, so the subproblems decouple. The combine term $p_{i - 1} p_{k} p_{j}$ (MCM) becomes $v_{i} v_{k} v_{j}$ (balloons) — same "three boundary values multiplied" shape. This same "try every split/root" pattern also drives Optimal Binary Search Tree.

L5.2 — Design a variant: minimize the maximum single multiplication

Instead of minimizing the sum of scalar multiplications, suppose you want to minimize the largest single combine cost used in the whole plan (a "peak memory/latency" objective). Write the modified recurrence and compute the answer for $p = [10, 100, 5, 50]$ .

Recall Solution

Replace "sum then min" with "for each split take the max of the three pieces, then min over $k$ ": $M [i] [j] = min_{i \leq k < j} max (M [i] [k], M [k + 1] [j], p_{i - 1} p_{k} p_{j}), M [i] [i] = 0.$ Why max inside: the peak is the worst single operation along the way, so combining pieces takes the largest of {left's peak, right's peak, this combine}. Why min outside: we still get to choose the split, so we pick the one whose peak is smallest.

Compute for $p = [10, 100, 5, 50]$ ( $A_{1} (10 \times 100), A_{2} (100 \times 5), A_{3} (5 \times 50)$ ):

$M [1] [2] = p_{0} p_{1} p_{2} = 10 \cdot 100 \cdot 5 = 5000$
$M [2] [3] = p_{1} p_{2} p_{3} = 100 \cdot 5 \cdot 50 = 25000$
$M [1] [3]$ :
- $k = 1$ : $max (M [1] [1], M [2] [3], p_{0} p_{1} p_{3}) = max (0, 25000, 50000) = 50000$
- $k = 2$ : $max (M [1] [2], M [3] [3], p_{0} p_{2} p_{3}) = max (5000, 0, 2500) = 5000$
- min $= 5000$ at $k = 2$ .

So the minimum peak is $5000$ with $(A_{1} A_{2}) A_{3}$ . Insight: the recurrence skeleton (interval DP, split at $k$ ) is untouched — only the aggregation operators changed (sum→max). Recognising that "the paradigm is the split, the objective is swappable" is the L5 mastery point.

Recall Quick self-test recap

Fill by increasing chain length? ::: Yes — $L = 2 \dots n$ , never row by row. Combine cost for split $k$ on $A_{i} \dots A_{j}$ ? ::: $p_{i - 1} p_{k} p_{j}$ . Number of parenthesizations of $n$ matrices? ::: Catalan $C_{n - 1}$ . How to switch MCM into "minimize peak cost"? ::: Replace inner sum with max, keep the outer min. Interval-DP golden rule? ::: Fix the LAST event so subproblems decouple.

Connections

Dynamic Programming — optimal substructure + overlapping subproblems
Catalan Numbers — counts the $C_{n - 1}$ parenthesizations (L4.1)
Burst Balloons — same interval DP, fix the last burst (L5.1)
Optimal Binary Search Tree — "try every root" interval DP
Memoization vs Tabulation — L4.2 top-down equivalence
Time Complexity Analysis — $O (n^{3})$ from three nested loops