# Matrix-Chain Multiplication ## Definition Given a chain $\langle A_1, A_2, \dots, A_n \rangle$ of $n$ matrices, $A_i$ has dimension $p_{i-1} \times p_i$, fully parenthesize the product to minimize amount of scalar multiplications. Input is a sequence of dimensions $\langle p_0, p_1, p_2, \dots, p_n \rangle$. ## Solution Brute force takes exponential time. Let $A_{i:j}$ denote the matrix results from evaluating $A_iA_{i+1}\cdots A_j$, $m[i, j]$ be the minimum number of scalar multiplications needed to compute $A_{i:j}$, $s[i, j]$ be the optimal split $k$. $ m[i, j] = \begin{cases} 0, & i = j, \\ \min\{ m[i, k] + m[k + 1, j] + p_{i-1}p_kp_j : i \le k < j \}, & i < j \end{cases} $ Compute shorter chains to longer chains: chain of length $1$ (trivial), $2$, and all the way up to $n$.