矩阵链乘法

矩阵乘法满足结合律，但不同括号化顺序的计算量可能差几个数量级。矩阵链乘法要找的不是乘积本身，而是最便宜的计算顺序。

设

$$A_i\text{ 的维度为 }p_{i-1}\times p_i,\qquad 1\le i\le n.$$

一个 $a\times b$ 矩阵乘以 $b\times c$ 矩阵，需要 $abc$ 次标量乘法。

1. 为什么贪心不可靠

“先乘眼前代价最小的一对”只看当前一步，却改变了中间矩阵的维度，可能让后续代价暴涨。真正需要考虑的是整个区间在最后一次乘法处怎样切开。

2. 状态与转移

令

$$m[i][j]=A_iA_{i+1}\cdots A_j\text{ 的最少乘法次数}.$$

若最后一次把区间分在 $k$ 与 $k+1$ 之间，那么左右两侧先各自算完，再把一个 $p_{i-1}\times p_k$ 矩阵与 $p_k\times p_j$ 矩阵相乘：

$$m[i][j]=\min_{i\le k<j} \left\{m[i][k]+m[k+1][j]+p_{i-1}p_kp_j\right\}.$$

单个矩阵无需乘法：$m[i][i]=0$。

3. 填表顺序

状态依赖更短区间，所以按区间长度递增：

for length = 2..n:
    for i = 1..n-length+1:
        j = i + length - 1
        m[i][j] = infinity
        for k = i..j-1:
            try split k

共有 $O(n^2)$ 个区间，每个枚举 $O(n)$ 个分割点：

$$T=O(n^3),\qquad S=O(n^2).$$

4. 一个直观例子

设

$$A_1:10\times100,\quad A_2:100\times5,\quad A_3:5\times50.$$

两种括号化：

$$(A_1A_2)A_3:10\cdot100\cdot5+10\cdot5\cdot50=7500,$$ $$A_1(A_2A_3):100\cdot5\cdot50+10\cdot100\cdot50=75000.$$

结果相同，代价却相差十倍。

5. 恢复最优括号化

另设 $s[i][j]$ 记录取得最小值的分割点 $k$。递归输出：

• $i=j$ 时输出 $A_i$；
• 否则输出左括号、区间 $[i,s[i][j]]$、区间 $[s[i][j]+1,j]$、右括号。

若多个 $k$ 同价，可任选一个；若要求所有最优方案，则要保留全部最优分割点。

6. 正确性

最优括号化的最后一次乘法必定把矩阵链分成两个连续子链。如果任一子链不是自身最优的，就能替换成更便宜的括号化，使总成本更低，矛盾。因此枚举最后分割点覆盖所有最优可能。

7. 区间 DP 的识别方式

矩阵链乘法代表一类常见模型：

• 状态是一段连续区间；
• 决策是选一个分割点；
• 大区间由左右小区间合并；
• 按区间长度递增计算。

石子合并、最优三角剖分、括号匹配计数等题也常用这套结构。