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{array}{ll}0& i=j\\ \underset{i\le k<j}{\min }(m[i,k]+m[k+1,j]+p_{i-1}{p}_k{p}_j)& i<j\end{array}$$

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=⟨30,35,15,5,10,20,25⟩$ (so $A_1$ is $30\times 35$, …, $A_6$ is $20\times 25$). Filling $m$ by chain length gives $m[1,6]=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.