矩阵连乘问题
问题建模
设维度数组 P=\langle p_0,p_1,\dots,p_n\rangle ，其中A_i的尺寸为 p_{i-1}\times p_i。
状态定义
m[i][j]：把子链A_i\cdots A_j 相乘所需的最少标量乘法次数（记为“备忘录/最优值表”）。
s[i][j]：达到最优时的分割位置 k（记为“标记函数/决策表”）。
边界
m[i][i]=0（单个矩阵无需乘法）。
状态转移方程
当i<j 时，在所有断点 k\in[i,\,j-1] 里取最好：
m[i][j]=\min_{i\le k<j}\Big(m[i][k]+m[k+1][j]+p_{i-1}\,p_k\,p_j\Big)
并记录取得最小值的 k 到 s[i][j]。
伪代码
MatrixChainOrder(p[0..n]):
for i = 1..n:
m[i][i] = 0
for L = 2..n: // 子链长度
for i = 1..n-L+1:
j = i + L - 1
m[i][j] = +∞
for k = i..j-1:
q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
if q < m[i][j]:
m[i][j] = q
s[i][j] = k
return m, s复杂度
时间复杂度： \mathcal{O}(n^3)
空间复杂度： \mathcal{O}(n^2)
带入实例构造表格
给定 P=\langle 50,10,40,30,5,20,15\rangle，n=6
各矩阵尺寸：
A1:50×10, A2:10×40, A3:40×30, A4:30×5, A5:5×20, A6:20×15
最优值表M
分割表S（记录最优值k）
\textbf{Length }L=2:\quad \\ \begin{aligned} m_{1,2}&=50\cdot10\cdot40=20000,\\ m_{2,3}&=10\cdot40\cdot30=12000,\\ m_{3,4}&=40\cdot30\cdot5=6000,\\ m_{4,5}&=30\cdot5\cdot20=3000,\\ m_{5,6}&=5\cdot20\cdot15=1500. \end{aligned}
\textbf{Length }L=3:\quad \\ \begin{aligned} m_{1,3}&=\min\left\{ \begin{aligned} & m_{1,1}+m_{2,3}+p_0p_1p_3, && m_{1,2}+m_{3,3}+p_0p_2p_3 \end{aligned}\right\}\\ &=\min\left\{ \begin{aligned} & 0+12000+50\cdot10\cdot30, && 20000+0+50\cdot40\cdot30 \end{aligned}\right\}\\ &=\min\{27000,80000\}=27000,\\[6pt] m_{2,4}&=\min\left\{ \begin{aligned} & m_{2,2}+m_{3,4}+p_1p_2p_4, && m_{2,3}+m_{4,4}+p_1p_3p_4 \end{aligned}\right\}\\ &=\min\left\{ \begin{aligned} & 0+6000+10\cdot40\cdot5, && 12000+0+10\cdot30\cdot5 \end{aligned}\right\}\\ &=\min\{8000,13500\}=8000,\\[6pt] m_{3,5}&=\min\left\{ \begin{aligned} & m_{3,3}+m_{4,5}+p_2p_3p_5, && m_{3,4}+m_{5,5}+p_2p_4p_5 \end{aligned}\right\}\\ &=\min\left\{ \begin{aligned} & 0+3000+40\cdot30\cdot20, && 6000+0+40\cdot5\cdot20 \end{aligned}\right\}\\ &=\min\{27000,10000\}=10000,\\[6pt] m_{4,6}&=\min\left\{ \begin{aligned} & m_{4,4}+m_{5,6}+p_3p_4p_6, && m_{4,5}+m_{6,6}+p_3p_5p_6 \end{aligned}\right\}\\ &=\min\left\{ \begin{aligned} & 0+1500+30\cdot5\cdot15, && 3000+0+30\cdot20\cdot15 \end{aligned}\right\}\\ &=\min\{3750,12000\}=3750. \end{aligned}
\textbf{Length }L=4:\quad \\ \begin{aligned} m_{1,4}&=\min\left\{ \begin{aligned} & m_{1,1}+m_{2,4}+p_0p_1p_4, && m_{1,2}+m_{3,4}+p_0p_2p_4,\\ &&& m_{1,3}+m_{4,4}+p_0p_3p_4 \end{aligned}\right\}\\ &=\min\left\{ \begin{aligned} & 0+8000+50\cdot10\cdot5, && 20000+6000+50\cdot40\cdot5,\\ &&& 27000+0+50\cdot30\cdot5 \end{aligned}\right\}\\ &=\min\{10500,36000,34500\}=10500,\\[6pt] m_{2,5}&=\min\left\{ \begin{aligned} & m_{2,2}+m_{3,5}+p_1p_2p_5, && m_{2,3}+m_{4,5}+p_1p_3p_5,\\ &&& m_{2,4}+m_{5,5}+p_1p_4p_5 \end{aligned}\right\}\\ &=\min\left\{ \begin{aligned} & 0+10000+10\cdot40\cdot20, && 12000+3000+10\cdot30\cdot20,\\ &&& 8000+0+10\cdot5\cdot20 \end{aligned}\right\}\\ &=\min\{18000,21000,9000\}=9000,\\[6pt] m_{3,6}&=\min\left\{ \begin{aligned} & m_{3,3}+m_{4,6}+p_2p_3p_6, && m_{3,4}+m_{5,6}+p_2p_4p_6,\\ &&& m_{3,5}+m_{6,6}+p_2p_5p_6 \end{aligned}\right\}\\ &=\min\left\{ \begin{aligned} & 0+3750+40\cdot30\cdot15, && 6000+1500+40\cdot5\cdot15,\\ &&& 10000+0+40\cdot20\cdot15 \end{aligned}\right\}\\ &=\min\{21750,10500,22000\}=10500. \end{aligned}
\textbf{Length }L=5:\quad \\ \begin{aligned} m_{1,5}&=\min\left\{ \begin{aligned} &m_{1,1}+m_{2,5}+p_0p_1p_5, && m_{1,2}+m_{3,5}+p_0p_2p_5,\\ &m_{1,3}+m_{4,5}+p_0p_3p_5, && m_{1,4}+m_{5,5}+p_0p_4p_5 \end{aligned}\right\}\\ &=\min\left\{ \begin{aligned} &0+9000+50\cdot10\cdot20, && 20000+10000+50\cdot40\cdot20,\\ &27000+3000+50\cdot30\cdot20, && 10500+0+50\cdot5\cdot20 \end{aligned}\right\}\\ &=\min\{19000,70000,60000,15500\}=15500,\\[6pt] m_{2,6}&=\min\left\{ \begin{aligned} &m_{2,2}+m_{3,6}+p_1p_2p_6, && m_{2,3}+m_{4,6}+p_1p_3p_6,\\ &m_{2,4}+m_{5,6}+p_1p_4p_6, && m_{2,5}+m_{6,6}+p_1p_5p_6 \end{aligned}\right\}\\ &=\min\left\{ \begin{aligned} &0+10500+10\cdot40\cdot15, && 12000+3750+10\cdot30\cdot15,\\ &8000+1500+10\cdot5\cdot15, && 9000+0+10\cdot20\cdot15 \end{aligned}\right\}\\ &=\min\{16500,20250,10250,12000\}=10250. \end{aligned}
\textbf{Length }L=6:\quad \\ \begin{aligned} m_{1,6}&=\min\left\{ \begin{aligned} &m_{1,1}+m_{2,6}+p_0p_1p_6, && m_{1,2}+m_{3,6}+p_0p_2p_6,\\ &m_{1,3}+m_{4,6}+p_0p_3p_6, && m_{1,4}+m_{5,6}+p_0p_4p_6,\\ &&& m_{1,5}+m_{6,6}+p_0p_5p_6 \end{aligned}\right\}\\ &=\min\left\{ \begin{aligned} &0+10250+50\cdot10\cdot15, && 20000+10500+50\cdot40\cdot15,\\ &27000+3750+50\cdot30\cdot15, && 10500+1500+50\cdot5\cdot15,\\ &&& 15500+0+50\cdot20\cdot15 \end{aligned}\right\}\\ &=\min\{17750,60500,53250,15750,30500\}=15750. \end{aligned}
所以：
m[1][6]=15750
这“15750”就是整条矩阵链 A_1A_2A_3A_4A_5A_6 的最小乘法次数。
同时，从上面的比较我们还能读出最优切法是 k=4，也就是先算 (A_1A_2A_3A_4) 和 (A_5A_6) 各自最优，然后把它们乘起来。继续往下递归会得到括号：
((A_1 (A_2 (A_3 A_4))) (A_5 A_6))