- 课程学习获取 90% 退款
- 技术教程
- 面试准备
菜单
返回探索页面
—
#### 问题背景
让我们一起来探索动态规划中的一个经典问题——矩阵链乘法（Matrix Chain Multiplication）。
我们给定一个由 $n$ 个矩阵组成的序列：$\langle A1, A2, \dots, A_n \rangle$。我们的目标是对这些矩阵进行完全加括号，使得计算该乘积所需的标量乘法次数最少。
这里所谓的“完全加括号”，是指将矩阵序列要么单独视为一个整体，要么递归地拆分成两个完全加括号的子序列。此外，矩阵的乘法满足结合律，因此无论我们如何加括号，计算出的最终结果都是相同的，但不同的加括号方式会导致计算过程中的中间代价（即标量乘法次数）截然不同。
#### 问题示例
假设我们有一个包含 4 个矩阵的链：$A1, A2, A3, A4$，它们的维度分别为：
- $A_1$: $5 \times 4$
- $A_2$: $4 \times 6$
- $A_3$: $6 \times 2$
- $A_4$: $2 \times 7$
我们需要找出计算 $A1 \cdot A2 \cdot A3 \cdot A4$ 的最优加括号方式。
#### 可能的加括号方案
对于 $n=4$ 的情况，一共有 5 种不同的完全加括号方案：
- $(A1(A2(A3 A4)))$
- $(A1((A2 A3)A4))$
- $((A1 A2)(A3 A4))$
- $((A1(A2 A3))A4)$
- $(((A1 A2)A3)A4)$
让我们来计算一下每种方案所需的标量乘法次数，看看哪一种最高效。
#### 方案 1: $(A1(A2(A3 A4)))$
- 计算 $A3 A4$
维度：$(6 \times 2) \times (2 \times 7) = 6 \times 7$
代价：$6 \times 2 \times 7 = 84$
- 计算 $A2 (A3 A_4)$
维度：$(4 \times 6) \times (6 \times 7) = 4 \times 7$
代价：$4 \times 6 \times 7 = 168$
- 计算 $A1 (A2 (A3 A4))$
维度：$(5 \times 4) \times (4 \times 7) = 5 \times 7$
代价：$5 \times 4 \times 7 = 140$
总代价：$84 + 168 + 140 = 392$
#### 方案 2: $(A1((A2 A3)A4))$
- 计算 $A2 A3$
维度：$(4 \times 6) \times (6 \times 2) = 4 \times 2$
代价：$4 \times 6 \times 2 = 48$
- 计算 $(A2 A3) A_4$
维度：$(4 \times 2) \times (2 \times 7) = 4 \times 7$
代价：$4 \times 2 \times 7 = 56$
- 计算 $A1 ((A2 A3) A4)$
维度：$(5 \times 4) \times (4 \times 7) = 5 \times 7$
代价：$5 \times 4 \times 7 = 140$
总代价：$48 + 56 + 140 = 244$
#### 方案 3: $((A1 A2)(A3 A4))$
- 计算 $A1 A2$
维度：$(5 \times 4) \times (4 \times 6) = 5 \times 6$
代价：$5 \times 4 \times 6 = 120$
- 计算 $A3 A4$
维度：$(6 \times 2) \times (2 \times 7) = 6 \times 7$
代价：$6 \times 2 \times 7 = 84$
- 计算 $(A1 A2) (A3 A4)$
维度：$(5 \times 6) \times (6 \times 7) = 5 \times 7$
代价：$5 \times 6 \times 7 = 210$
总代价：$120 + 84 + 210 = 414$
#### 方案 4: $((A1(A2 A3))A4)$
- 计算 $A2 A3$
维度：$(4 \times 6) \times (6 \times 2) = 4 \times 2$
代价：$4 \times 6 \times 2 = 48$
- 计算 $A1 (A2 A_3)$
维度：$(5 \times 4) \times (4 \times 2) = 5 \times 2$
代价：$5 \times 4 \times 2 = 40$
- 计算 $(A1 (A2 A3)) A4$
维度：$(5 \times 2) \times (2 \times 7) = 5 \times 7$
代价：$5 \times 2 \times 7 = 70$
总代价：$48 + 40 + 70 = 158$
#### 方案 5: $(((A1 A2)A3)A4)$
- 计算 $A1 A2$
维度：$(5 \times 4) \times (4 \times 6) = 5 \times 6$
代价：$5 \times 4 \times 6 = 120$
- 计算 $(A1 A2) A_3$
维度：$(5 \times 6) \times (6 \times 2) = 5 \times 2$
代价：$5 \times 6 \times 2 = 60$
- 计算 $((A1 A2) A3) A4$
维度：$(5 \times 2) \times (2 \times 7) = 5 \times 7$
代价：$5 \times 2 \times 7 = 70$
总代价：$120 + 60 + 70 = 250$
结论
通过对比上述五种方案，我们可以清楚地看到：
- 方案 4 $((A1(A2 A3))A4)$ 的总代价为 158，是所有方案中最小的。
- 方案 3 $((A1 A2)(A3 A4))$ 的总代价为 414，是所有方案中最大的。
由此可见，即便计算结果的矩阵维度相同，不同的计算顺序对性能的影响也是巨大的。我们的目标正是通过算法找到那个最优的顺序。
动态规划解题思路
为了找到最优解，我们可以使用动态规划。我们定义 $m[i, j]$ 为计算矩阵 $Ai \dots Aj$ 所需的最小标量乘法次数。
- 最优子结构
如果我们将链在 $k$ 处断开（$i \le k < j$），那么最小代价 $m[i, j]$ 等于左边子链 $Ai \dots Ak$ 的最小代价加上右边子链 $A{k+1} \dots Aj$ 的最小代价，再加上这两部分结果矩阵相乘的代价。
公式表示为：
$$m[i, j] = \min{i \le k < j} \{ m[i, k] + m[k+1, j] + p{i-1} pk pj \}$$
其中，$p$ 是存储各矩阵维度的数组，矩阵 $Ai$ 的维度为 $p{i-1} \times p_i$。
- 计算顺序
我们按照子链的长度 $L$ 从 2 到 $n$ 递增计算。对于每个长度 $L$，计算所有可能的连续 $L$ 个矩阵的子链的最小代价。
代码实现思路
虽然我们不直接展示代码，但实现逻辑通常如下：
- 初始化一个二维数组 INLINECODEe7435ef3 或 INLINECODE1282c3bf，对角线元素为 0（因为单个矩阵不需要乘法）。
- 外层循环遍历链的长度 INLINECODE0e63f908 从 2 到 INLINECODE3657343f。
- 内层循环遍历起始索引 INLINECODE61dfa35c，计算结束索引 INLINECODEbfa896a9。
- 在最内层循环中，尝试在 INLINECODE4ba5fc96 和 INLINECODE539f9611 之间的每一个 INLINECODEf8ef8f86 处断开，利用上述递推公式更新 INLINECODEe0081b1a 的最小值。
- 最终，
dp[1][n]存储的就是整个矩阵链乘法的最小代价。
通过这种方法，我们可以将时间复杂度控制在 $O(n^3)$，这比暴力枚举所有可能的组合要高效得多。
希望这次探索能帮助你更好地理解矩阵链乘法问题及其动态规划解法！