3.6 矩阵链乘法

这一篇继续动态规划，讲矩阵链乘法。它和加权区间调度结构不同——它展示的是 DP 的另一种典型形态：区间 DP（子问题用一段区间 $[i,j]$ 刻画，而非一个前缀）。它还把第二卷 Strassen（2.5）提过的"矩阵乘法代价"用上了：相同的一串矩阵相乘，加括号的顺序不同，标量乘法次数天差地别。

1.问题：怎么加括号最省

给一串矩阵 $A_1 A_2 \cdots A_n$ 相乘（维度相容， $A_i$ 是 $p_{i-1}\times p_i$ ）。矩阵乘法满足结合律，所以加括号的方式有很多种，结果相同，但计算量不同。

举个经典例子：三个矩阵 $A_{10\times100}\, B_{100\times5}\, C_{5\times50}$ 。

$(AB)C$ ： $AB$ 算出 $10\times5$ ，代价 $10\cdot100\cdot5=5000$ ；再乘 $C$ 代价 $10\cdot5\cdot50=2500$ ；共 $7500$ 。
$A(BC)$ ： $BC$ 代价 $100\cdot5\cdot50=25000$ ；再 $A$ 乘结果代价 $10\cdot100\cdot50=50000$ ；共 $75000$ 。

差了 10 倍！ 同样的乘积，加括号顺序不同，计算量差一个数量级。我们要找让总标量乘法次数最少的加括号方式。

2.朴素枚举：卡特兰数，爆炸

加括号方式的数量是卡特兰数 $C_{n-1}$ ，增长极快（ $n=20$ 时已超 $10^{10}$ ）。枚举所有加括号方式不可行。但注意：很多加括号方式会重复计算相同的子链乘积——这就是重叠子问题，DP 的用武之地。

3.状态：一段区间的最少代价

定义 $m[i,j]$ = 计算 $A_i\cdots A_j$ （这一段）所需的最少标量乘法次数。这是区间 DP——状态用区间 $[i,j]$ 刻画，不是前缀。

基底： $m[i,i]=0$ （单个矩阵不用乘）。

转移：要算 $A_i\cdots A_j$ ，最后一步一定是在某个位置 $k$ 断开（先算左边 $A_i\cdots A_k$ 、再算右边 $A_{k+1}\cdots A_j$ 、再把两个结果相乘）。遍历所有断点 $k$ ：

m[i,j]=\min_{i\le k<j}\Big(m[i,k]+m[k+1,j]+p_{i-1}p_kp_j\Big)

三项分别是：左半代价、右半代价、最后合并的代价（左半结果是 $p_{i-1}\times p_k$ 、右半是 $p_k\times p_j$ ，相乘代价 $p_{i-1}p_kp_j$ ）。取所有 $k$ 里的最小。

4.填表顺序：按区间长度

关键细节： $m[i,j]$ 依赖更短的区间 $m[i,k]$ 和 $m[k+1,j]$ （ $k<j$ ）。所以填表要按区间长度从小到大——先填所有长度 2 的，再长度 3……最后长度 $n$ 。

MATRIX-CHAIN-ORDER(p)
    for i = 1 to n: m[i,i] = 0
    for L = 2 to n:              // L 是区间长度
        for i = 1 to n-L+1:
            j = i + L - 1
            m[i,j] = ∞
            for k = i to 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[1,n]

三重循环，复杂度 $O(n^3)$ ；空间 $O(n^2)$ 。记一张断点表 $s[i,j]$ ，事后能还原出最优加括号方式。

5.区间 DP 这个模式的普适性

矩阵链乘法确立了一个极其重要的 DP 模式——区间 DP：状态是一段区间 $[i,j]$ ，转移是"在区间里找个断点 $k$ 分成两半"。这个模式在很多问题里复现：

石子合并：把一堆石子合并，每次合并代价是两堆之和，求最小总代价。
最优二叉搜索树：给一组键的搜索频率，构造让期望搜索代价最小的 BST。
回文串划分：把字符串划分成最少回文子串。

识别出"问题的子结构是一段区间、能在中间找个断点"这个特征，就往区间 DP 上靠。第十一卷 11.2 会把它提炼成"分解法"。这是 DP 三大典型结构之一（另两个是线性 DP 如背包、树形 DP）。

6.练习

Q1. 矩阵链 $A_{1}(10\times100)\, A_2(100\times5)\, A_3(5\times50)$ ，用 DP 求最少乘法次数和最优断点。

$m[1,1]=m[2,2]=m[3,3]=0$ 。长度 2： $m[1,2]=10\cdot100\cdot5=5000$ ， $m[2,3]=100\cdot5\cdot50=25000$ 。长度 3： $m[1,3]=\min(m[1,1]+m[2,3]+p_0p_1p_3,\ m[1,2]+m[3,3]+p_0p_2p_3)=\min(0+25000+10\cdot100\cdot50,\ 5000+0+10\cdot5\cdot50)=\min(75000,7500)=7500$ ，断点 $k=1$ 。即 $(A_1A_2)A_3$ ，共 7500 次。和第 1 节的手算吻合。

Q2. 矩阵链乘法的状态转移为什么是 $m[i,j]=\min_k(m[i,k]+m[k+1,j]+p_{i-1}p_kp_j)$ ？三项分别是什么？

最后一次乘法一定把链在某处 $k$ 断开：左半 $A_i\cdots A_k$ （结果 $p_{i-1}\times p_k$ ）、右半 $A_{k+1}\cdots A_j$ （结果 $p_k\times p_j$ ），合并代价 $p_{i-1}p_kp_j$ 。总代价 = 左半最优 $m[i,k]$ + 右半最优 $m[k+1,j]$ + 合并 $p_{i-1}p_kp_j$ 。遍历所有 $k$ 取最小。三项对应这三部分。

Q3.（思考题） 朴素枚举加括号方式是卡特兰数（指数级），DP 为什么能做到 $O(n^3)$ ？

因为不同加括号方式会重复计算相同的子链（如 $A_1A_2A_3$ 和 $A_1(A_2A_3)$ 都要算 $A_2A_3$ ）。DP 用 $m[i,j]$ 把每个子链的最优代价只算一次、缓存复用，把指数级的重复计算压成多项式。这正是 DP"重叠子问题"的价值——相对朴素递归省掉所有重复。 $O(n^3)$ 来自区间数 $O(n^2)$ × 每个区间的断点数 $O(n)$ 。

7.小结

矩阵链乘法用区间 DP， $O(n^3)$ 求出最少乘法次数的最优加括号方式。状态 $m[i,j]$ 是一段区间的最优，转移在区间里找断点 $k$ 。它确立了"区间 DP"这个普适模式（石子合并、最优 BST 等都复用）。下一篇我们看 DP 最经典的应用——0/1 背包。