Matrix-chain multiplication

The problem

Matrix multiplication is associative — $(A_1 A_2) A_3 = A_1 (A_2 A_3)$ — so the *result* never changes, but the cost can change wildly. Multiplying a $p\times q$ matrix by a $q\times r$ matrix costs $p \cdot q \cdot r$ scalar multiplications. Given a chain $A_1 A_2 \cdots A_n$ where $A_i$ is $p_{i-1}\times p_i$, find the parenthesization that minimizes total scalar multiplications.

Brute force is hopeless: the number of parenthesizations grows like $\Omega(4^n / n^{3/2})$ (the Catalan numbers).

Optimal substructure

Any parenthesization of $A_i \cdots A_j$ splits at some $k$ into $(A_i\cdots A_k)(A_{k+1}\cdots A_j)$. By cut-and-paste, both halves must themselves be optimally parenthesized. Let $m[i,j]$ be the minimum cost for $A_i\cdots A_j$: $$m[i,j] = \begin{cases} 0 & i = j \\ \displaystyle\min_{i \le k < j}\big(m[i,k] + m[k+1,j] + p_{i-1}\,p_k\,p_j\big) & i < j \end{cases}$$

The extra term $p_{i-1}p_k p_j$ is the cost of the final multiply of the two sub-products (a $p_{i-1}\times p_k$ result times a $p_k\times p_j$ result).

Fill order is by CHAIN LENGTH, not by index

Computing $m[i,j]$ needs $m[i,k]$ and $m[k+1,j]$, which both cover shorter chains. So fill in order of increasing chain length $\ell = 2,3,\dots,n$ — never by raw index. This is the reverse-topological order of the subproblem graph.

Worked example

Six matrices with dimension vector $p = \langle 30,35,15,5,10,20,25\rangle$ (so $A_1$ is $30\times35$, …, $A_6$ is $20\times25$). Filling $m$ by chain length gives $m[1,6] = \mathbf{15125}$ scalar multiplications, achieved by $((A_1 (A_2 A_3))((A_4 A_5) A_6))$ — versus 120 750+ for a bad order on the same chain. Store a split table $s[i,j]=k$ alongside $m$ to reconstruct the parenthesization via PRINT-OPTIMAL-PARENS.

Cost

$\Theta(n^2)$ subproblems (pairs $i\le j$), up to $n$ split choices each $\Rightarrow \Theta(n^3)$ time, $\Theta(n^2)$ space.