企业官网建设流程全解析

如果你第一次接触矩阵链乘法，可能觉得这无非是个加括号的问题，三个矩阵还能有什么区别。但实际跑一个规模很小的例子就能把人吓一跳：三个矩阵A1、A2、A3的维度分别是10×100、100×5、5×50，按“先算前两个再乘第三个”的顺序做，一共需要7500次标量乘法；如果换成“先算后两个再乘第一个”，则是75000次——整整10倍差距。矩阵数量一多，不同加括号方式的计算代价差距还会继续拉大，甚至呈现指数级别的悬殊。矩阵链乘法要解决的就是这么一件事：给定一个矩阵链，找出计算代价最小的加括号方案。而它也是区间动态规划（区间DP）最经典的入门题，没有之一。

我当年学这道题的时候，曾以为它和普通的背包DP没什么两样，直到真正动手写代码才发现，区间DP的填表顺序、状态定义和边界处理都有不少门道。这篇文章我就把完整的推导过程、代码实现、常见坑和一点点进阶优化全部摊开来讲，适合刚学动态规划、想用一道经典题彻底搞懂区间DP思路的读者。

1. 矩阵链代价的度量方式，以及问题如何被严格定义

1.1 一次标量乘法到底怎么计数

要理解这个问题，先得明白两个矩阵相乘的计算代价怎么算。假设A是i×j的矩阵，B是j×k的矩阵，乘积C是i×k的矩阵。用最普通的三重循环实现乘法时，内层循环总共会执行i×j×k次标量乘法和同样数量级的加法。我们通常只统计标量乘法的次数，即代价为ijk。

这里有个容易混淆的地方：很多人以为结果矩阵C有i×k个元素，代价就是i×k，忘了每个元素都要做j次乘加。i、j、k三个维度全都要乘进去，一个都不能少。

for (int x = 0; x < i; x++) { for (int y = 0; y < k; y++) { float sum = 0.0f; for (int z = 0; z < j; z++) { sum += A[x][z] * B[z][y]; } C[x][y] = sum; } }

这段代码里最内层语句执行的次数，就是ijk。

1.2 三个矩阵的例子为什么能差10倍

回到开头那个例子。三个矩阵维度分别是10×100、100×5、5×50，两种加括号方式的代价拆解如下：

明明最后得到的是同一个结果矩阵，但计算量差了10倍。原因在于中间结果矩阵的维度完全不同：(A1A2)得到一个10×5的矩阵，而(A2A3)得到一个100×50的矩阵，后者在做最终乘法时，维度i和k全都被放大了。

矩阵乘法满足结合律，任何加括号方式得到的结果在数学上都相同（浮点数舍入误差的差异这里不考虑），但不同加括号方式对应的计算代价天差地别。问题就来了：给定n个矩阵A1, A2, ..., An，如何加括号，才能让总标量乘法次数最少？

1.3 用维度数组p把矩阵链形式化

为了在代码里描述矩阵链，我们需要一个紧凑的表示方法。n个矩阵需要n+1个维度值：用数组p[0..n]表示，其中矩阵Ai的维度是p[i-1]×p[i]。比如上面的例子，p = [10, 100, 5, 50]，A1是10×100，A2是100×5，A3是5×50。

这样表示的原因很直观：相邻矩阵能相乘，必须满足Ai的列数等于A{i+1}的行数，也就是p[i]这个值同时承担了“Ai的列数”和“A{i+1}的行数”两个身份。只要p数组给定，整个矩阵链的合法性和维度信息就完全确定了，这也是后面所有DP状态转移的基石。

2. 凭直觉做的话，贪心和暴力枚举为什么都会翻车

2.1 贪心策略的反例：局部最便宜不等于全局最优

很多人第一反应是：每次挑代价最小的相邻乘法先算，这不就是最优的吗？听上去符合直觉，但实际不堪一击。我构造一个简单的反例。

考虑4个矩阵，维度分别是A1: 10×1，A2: 1×10，A3: 10×1，A4: 1×10。按贪心思路，先计算所有相邻乘法的代价：

• A1A2：10×1×10 = 100
• A2A3：1×10×1 = 10
• A3A4：10×1×10 = 100

贪心会先选代价最小的A2A3（代价10），得到一个新的10×1矩阵。此时矩阵链变成：A1(10×1)、新矩阵(10×1)、A4(1×10)，对应p数组变成[10, 1, 1, 10]？不对，这里的表达还不够直观，我们按p数组重新看。原链p = [10, 1, 10, 1, 10]，A1=10×1，A2=1×10，A3=10×1，A4=1×10。

合并A2A3后，新矩阵是1×1（p[1]×p[3]？这里p的下标会乱）。为了不乱，直接算代价：

• 方案一：贪心先合并A2A3(代价10)，新矩阵1×1。链变成A1(10×1)、新(1×1)、A4(1×10)。下一步可选A1新(10×1×1=10)或新A4(1×1×10=10)，都是10。假设再合并A1和新(代价10)，得到10×1矩阵，最后乘A4：10×1×10=100。贪心总代价=10+10+100=120。
• 方案二：最优方案是先合并A1A2(100)和A3A4(100)，得到两个10×10矩阵，再相乘：10×10×10=1000？这样更差。

看起来这组数据贪心还赢了，说明我构造得不好。重新构造。我的目的是展示贪心的局部决策陷阱，但这里的反例不太好。思考一下，矩阵链乘法贪心确实可能失败，但临时构造反例容易出错。我不如用一个更通用的说法：贪心策略的问题在于，选择当前最小合并代价，可能会把一个维度很小的中间结果“锁死”，导致后续不得不反复做大维度乘法。但要用例子说清楚需要小心。

我自己先找一个可靠的反例。想了一下，可以用这个：p = [100, 1, 100, 1, 100]，即A1=100×1，A2=1×100，A3=100×1，A4=1×100。 贪心：

• 初始代价：A1A2=1001100=10000，A2A3=11001=100，A3A4=1001100=10000
• 选A2A3（代价100），得到1×1矩阵
• 链：A1(100×1), M(1×1), A4(1×100)
• 代价：A1M = 10011=100；MA4 = 11100=100；都是100，选一个，比如A1*M得到100×1矩阵，代价100
• 最后乘A4：100×1×100=10000
• 贪心总代价 = 100 + 100 + 10000 = 10200

最优方案：

• A1A2 = 1001100 = 10000，得到100×100矩阵
• A3A4 = 1001100 = 10000，得到100×100矩阵
• 两个100×100相乘 = 100100100 = 1000000 这个更差。看来贪心在这个例子上又赢了？

我换个思路：p = [10, 20, 5, 1, 10]，4个矩阵：A1=10×20, A2=20×5, A3=5×1, A4=1×10。 初始代价： A1A2 = 10205 = 1000 A2A3 = 2051 = 100 A3A4 = 5110 = 50 贪心选A3A4（50），得到5×10矩阵。链变成A1(10×20), A2(20×5), M(5×10)。 再算： A1A2 = 10205 = 1000 A2M = 20510 = 1000 贪心选A1A2（1000），得到10×5矩阵，再乘M(5×10)：105*10=500。 贪心总代价 = 50 + 1000 + 500 = 1550。

最优方案？用DP算： dp[1][2] = 1000 dp[2][3] = 2051 = 100 dp[3][4] = 5110 = 50 dp[1][3] = min(k=1: 0+100+10201=300; k=2: 1000+0+1051=1050) = 300 dp[2][4] = min(k=2: 0+50+20510=1050; k=3: 100+0+20110=300) = 300 dp[1][4] = min(k=1: 0+300+102010=2300; k=2: 1000+50+10510=1550; k=3: 300+0+10110=400) = 400

最优是400，对应k=3，方案是(A1(A2(A3A4)))？不对，k=3表示整体从A3A4分开，左段dp[1][3]=300（k=1，A1(A2A3)），右段A4。总代价300+0+10110=400。 分解：A2A3 = 2051=100，得到20×1；A1(10×20) * (20×1) = 10201=200，得到10×1；再乘A4(1×10) = 10110=100。总100+200+100=400。对。

贪心1550 vs 最优400，差了好几倍。这是可靠的反例。好，就用p = [10, 20, 5, 1, 10]。

贪心为什么错？因为贪心第一步选了A3A4（代价50），把A4的“小列数”提前消费掉了，后续A2A3合并时，中间结果变成20×1而不是20×5？实际后面A1*中间结果用了20... 不对，问题关键：合并顺序选择没有全局视角，当前代价最小不代表不会把后续乘法“逼”成大维度代价。不过解释时不用太较真，可以只说“贪心每一步只基于当前相邻代价，无法感知全局维度结构，很容易先吃掉最优解里的关键步骤”。

2.2 暴力枚举为什么也走不通：卡特兰数爆炸

那把所有加括号方案都枚举一遍行不行？行，但很快会爆炸。n个矩阵的合法加括号方案数，等于第n-1个卡特兰数Catalan(n-1)。卡特兰数的增长速度接近指数级乘常数，n=20时已经接近1.77×10^9，n=30时则远超任何机器能暴力枚举的范围。

卡特兰数的递推式C_0=1，C_n = Σ_{k=0}^{n-1} C_k * C_{n-k-1}。这个递推结构本身就暗示了矩阵链的递归拆解方式：把所有方案按“最后一个乘号的位置”分类，每一类左边k个矩阵的方案数乘以右边n-k个矩阵的方案数。这个分类思想在后面DP里会被直接复用，只是从“枚举全部方案”变成了“记录每个子问题的最优值”。

所以，朴素贪心不可靠，暴力枚举不可行，这就需要动态规划出场。

3. 最优子结构观察：最后一步永远是“一分为二”

3.1 核心观察

无论最优加括号方案长什么样，整个矩阵链的乘法一定有一个“最后执行”的乘法。这个最后一步把矩阵链分成了两部分：左边是A_i到A_k的乘积，右边是A_{k+1}到A_j的乘积，然后把这两个结果矩阵相乘。

由于左右两半内部也是合法的矩阵链乘法，它们各自的加括号方式也必须是各自的最优方案。这就是最优子结构：整体最优解包含子问题的最优解。如果左半部分有比当前方案代价更低的加括号方式，整个方案的代价还能更低，矛盾。因此，我们只需要递归地求每个子区间的最优代价，就可以组合出整个问题的最优解。

3.2 状态定义与转移方程

基于这个观察，定义状态dp[i][j]为“计算A_i × A_{i+1} × ... × A_j所需的最小标量乘法次数”。

• 边界条件：当i == j时，只有一个矩阵，不需要做任何乘法，dp[i][i] = 0。
• 当i < j时，枚举最后一个乘号的位置k（k从i到j-1），得到转移方程：

dp[i][j] = min_{i ≤ k < j} ( dp[i][k] + dp[k+1][j] + p[i-1] × p[k] × p[j] )

最后一项p[i-1] × p[k] × p[j]是合并左右两段结果的代价：左段结果矩阵维度是p[i-1]×p[k]，右段结果矩阵维度是p[k]×p[j]，两个矩阵相乘的成本就是p[i-1]·p[k]·p[j]。

拿前面p = [10, 20, 5, 1, 10]的例子，dp[1][4] = 400的更新路径是k=3：dp[1][3] + dp[4][4] + 10×1×10 = 300 + 0 + 100 = 400。这个直觉和计算都对得上。

3.3 为什么它叫“区间DP”

区间DP和普通线性DP最大的区别在于：状态表示的是原序列的一个连续子段，而不是一个单纯的前缀或位置。矩阵链乘法中，任意子问题都是矩阵链的连续一段“A_i到A_j”，所以状态天然是二维的区间[i, j]，转移则是把区间按某个点切成两段。

这带来一个直接后果：子问题之间不是按“位置从左到右”递推的，而是按“区间长度从短到长”递推。长区间的解依赖短区间的解，而短区间必须先被算好。理解这一点，是正确实现区间DP的钥匙。

4. 填表顺序是区间DP的命门：为什么必须按长度从小到大

4.1 依赖关系决定了递推次序

看转移方程，dp[i][j]依赖dp[i][k]和dp[k+1][j]。这两个子问题的区间都严格短于[i, j]，因为k在i和j之间，无论怎么切，左右两段的长度都小于j-i+1。

所以在计算dp[i][j]时，所有长度小于当前区间长度的dp值都必须已经算好了。最稳妥的填表策略就是：外层循环枚举区间长度len，从2到n；内层枚举区间起点i，然后根据len和i算出区间终点j = i + len - 1；最内层枚举分割点k。

如果反过来，先枚举i再枚举j，或者先枚举k再算i、j，就会出现dp[i][k]还是初始值的情况，得到的结果错得毫无规律。我第一次写的时候就是把i和j的循环放外面、长度放里面，结果一跑就全是垃圾值，排查半天才发现是循环顺序的问题。

4.2 正确填表的三重循环骨架

用伪代码描述正确结构：

for len = 2 to n: # 区间长度从小到大 for i = 1 to n - len + 1: j = i + len - 1 dp[i][j] = INF for k = i to j - 1: cost = dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j] if cost < dp[i][j]: dp[i][j] = cost

关于i的循环范围“1到n-len+1”这个写法经常有人写错。它保证的是当起点i取最大值时，终点j = i + len - 1恰好等于n，不会越界。比如n=5，len=3时，i最大能取3，对应的j=3+3-1=5；如果i取4，j就变成6，越界了。

4.3 为什么初始化是dp[i][i]=0而不是INF

长度为1的区间不需要计算，代价为0，这是所有递推的地基。而长度大于等于2的dp[i][j]在计算前应该设为一个足够大的数（比如float('inf')或者一个大于任何可行代价的整数），才能在枚举k的过程中不断取min。

有个细节：很多人只初始化dp[i][i]=0，忘了把其他dp[i][j]设为INF。在Python里如果全用0初始化，所有cost和0比较时往往第一个k就通过，但其它k如果算出一个更大的值也不会被正确比较，最终会影响更大的区间。所以正确做法是“长度1的区间置0，其余置INF，然后在填表时每次先置INF再枚举”。

5. 完整代码与括号重构：能跑出结果才算真会

5.1 基础实现：同时记录最优分割点

只求最小乘法次数还不够，通常我们还想知道具体怎么加括号。这就要求在每次更新dp[i][j]时，把对应的最优分割点k记录到一个辅助数组s[i][j]里。后面回溯s数组，就能递归地输出括号方案。

def matrix_chain_order(p): n = len(p) - 1 INF = float('inf') dp = [[0] * (n + 1) for _ in range(n + 1)] s = [[0] * (n + 1) for _ in range(n + 1)] # 区间长度从2到n for length in range(2, n + 1): for i in range(1, n - length + 2): j = i + length - 1 dp[i][j] = INF for k in range(i, j): cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j] if cost < dp[i][j]: dp[i][j] = cost s[i][j] = k return dp, s

注意dp和s的维度是(n+1)×(n+1)，下标从1开始使用。这里刻意留出下标0不用，纯粹是为了让代码里dp[i][k]、p[k]这些索引读起来顺。

5.2 回溯最优括号方案

有了s[i][j]，输出括号方案就是一个经典递归：

def print_parens(s, i, j): if i == j: print(f"A{i}", end="") else: print("(", end="") print_parens(s, i, s[i][j]) print("(", end="") print_parens(s, s[i][j] + 1, j) print(")", end="")

这段递归的逻辑是：如果区间只剩一个矩阵，直接输出Ai；否则先输出左括号，递归输出左半区间[s[i][j]]，再递归输出右半区间[s[i][j]+1, j]，最后补右括号。

这里特别容易写错的地方是右半区间的起点：不是s[i][j]+1而是什么？是k+1，而k就是s[i][j]。很多人直接把k当作右半段的终点，然后递归调用print_parens(s, i, k)和print_parens(s, k, j)，这样会重复输出同一个矩阵，括号结构乱成一团。

5.3 跑一个具体例子验证

用p = [10, 20, 5, 1, 10]跑一遍，期望结果是最小代价400，括号方案为(A1(A2(A3A4)))? 前面推出来是这样的：dp[1][4]=400对应k=3，dp[1][3]=300对应k=1，所以是((A1(A2A3))A4)? 等等，让我重新确认。

dp[1][3]=300对应k=1（A1 | A2A3），所以左半是A1，右半是(A2A3)。 dp[2][3]的选择：dp[2][3] = min(k=2: 0+0+2051=100; k=3不存在) = 100，s[2][3]=2，即A2A3。 所以dp[1][3] = dp[1][1] + dp[2][3] + p[0]p[1]p[3] = 0 + 100 + 10201 = 300。注意这个合并是(A1)(A2A3)的代价，即10×(20×1)=10201=200，合起来300。但前面我推导时写的是A1(A2A3)代价100(内部)+200(合并)=300。对。

整体dp[1][4] = dp[1][3] + dp[4][4] + p[0]p[3]p[4] = 300 + 0 + 10110 = 400。 这个k=3意味着最后一步：左边(A1A2A3)，右边A4。而左段内部是(A1(A2A3))。

所以括号方案是((A1(A2A3))A4)。验证代价：(A2A3) = 2051=100，得20×1；(A1*(20×1)) = 10201=200，得10×1；最后乘A4(1×10) = 10110=100；总400。对。

输出格式就是"((A1(A2A3))A4)"。

我手算的时候前面说“k=3，左段dp[1][3]=300（k=1，A1(A2A3)），右段A4”也验证了。好。

那我在文中给出的运行示例中，可以直接说调用matrix_chain_order后dp[1][4]为400，print_parens输出((A1(A2A3))A4)。为了严谨，我应该在文中把这段说明写清楚。

5.4 时间空间复杂度

基础实现是三重循环，外层长度O(n)，中层起点O(n)，内层分割点O(n)，总时间复杂度O(n^3)。空间上dp和s两个二维表都是O(n^2)。这个复杂度对n在几百量级的场景完全够用，如果n上千就要考虑Knuth优化。

6. Knuth优化：从O(n^3)压到O(n^2)的关键技巧

6.1 四边形不等式到底给了什么好处

矩阵链乘法满足四边形不等式，这意味着最优分割点s[i][j]具有单调性：

s[i][j-1] ≤ s[i][j] ≤ s[i+1][j]

这个性质在工程上的意义是：枚举分割点k时，不需要从i扫到j-1，只需要在s[i][j-1]到s[i+1][j]这个范围内枚举。别看只是把范围从“整个区间”缩到“两个邻居区间的最优分割点之间”，由于所有区间枚举k的总长度均摊下来是O(1)，整体复杂度能从O(n^3)降到O(n^2)。

这个优化的直觉可以这样理解：随着区间右端点右移，最优分割点不会向左回头；随着区间左端点左移，最优分割点也不会向右回头。它是一个“单调不回头”的搜索过程，所以可以把上一轮搜索得到的边界直接传给下一轮。

6.2 Knuth优化的实现要点

代码层面只需改动内层循环的起止位置，但边界处理很容易出错：

def matrix_chain_order_knuth(p): n = len(p) - 1 INF = float('inf') dp = [[0] * (n + 1) for _ in range(n + 1)] s = [[0] * (n + 1) for _ in range(n + 1)] for i in range(1, n + 1): s[i][i] = i for length in range(2, n + 1): for i in range(1, n - length + 2): j = i + length - 1 dp[i][j] = INF k_start = max(i, s[i][j - 1] if s[i][j - 1] else i) k_end = min(j - 1, s[i + 1][j] if s[i + 1][j] else j - 1) for k in range(k_start, k_end + 1): cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j] if cost < dp[i][j]: dp[i][j] = cost s[i][j] = k return dp[1][n]

代码里的max和min是为了防止边界情况越过合法范围。比如区间长度2时，s[i+1][j]是单点区间的最优分割点，值为i+1，但合法k最多只能到j-1=i，所以必须用min夹一下。这个细节如果漏掉，小测试能过，大测试就会越界访问。

Knuth优化不是所有DP都能用，它要求代价函数满足四边形不等式和单调性。在矩阵链乘法里，由于代价项p[i-1]×p[k]×p[j]的特殊结构，前提是成立的；但如果你拿到一个别的区间DP题，不能盲目套优化，需要先验证性质。验证的通用做法是用小规模暴力DP和优化DP对拍，一旦s[i][j]出现非单调的跳变，就说明该优化不适用。

7. 实战中常见的五个坑，每一个我都踩过

7.1 p数组的长度和含义搞反

p数组长度是n+1，不是2n，也绝对不是2n+1。每个矩阵只贡献一个“新维度”，第一个矩阵的“旧维度”由p[0]提供。比如5个矩阵，p的长度是6：p[0]到p[5]。很多人一看到“矩阵维度”就想到需要2n个数，其实只需要n+1个，因为相邻矩阵共享维度。

7.2 循环边界差一导致越界或漏算

i的取值范围是1到n-length+1，不是1到n，也不是1到n-length。忘记加1会导致最后一个起点被跳过，最终的dp[1][n]可能仍然是INF或者错误值。这类边界错误在调试时往往很难发现，因为大部分dp值看起来“差不多对”，只有最大区间错。建议写完代码后用n=3或n=4的小例子手算一遍对照。

7.3 数值溢出问题

矩阵乘法次数的增长非常快。n=30时，虽然dp值本身不一定特别大，但如果矩阵维度是几百几千，总代价轻松超过32位整数的上限。用C/C++写这道题必须用long long，如果竞赛题的维度范围给到10^4量级，long long也不够需要用更高精度。Python等脚本语言没有这个问题，但输出时也要留意值是否合理，避免“算对了看起来却像垃圾值”的困惑。

7.4 s数组记录分割点时的覆盖问题

s[i][j]应该只在cost严格小于dp[i][j]时更新。如果dp初始值不是INF，而是0，那么所有k的cost都不会小于0，s永远不会被写入有意义的值。另一种错误是把更新写在外层循环里，导致s[i][j]被最后一次k的值覆盖，而不是最优k的值。回溯括号方案时，这种错误会让输出变成一堆(A1(A1(A1...。

7.5 打印括号时的递归边界和重复输出

print_parens的递归终止条件是i==j，不是s[i][j]==0。因为长度为2的区间s[i][j]也有值，如果拿s[i][j]==0作为终止条件，长度2的区间会被无限递归或漏输出。此外，右半段的起点是s[i][j]+1，不是s[i][j]。这个+1特别容易漏，漏了之后输出会变成((A1A2)A2)这种明显不合理的方案，但很多人看到后第一反应是怀疑自己的DP求错了，而不是打印函数写错了。

我把常见坑整理成一张表，方便回顾：

8. 这个思维能带走的，不止是矩阵链本身

8.1 区间DP的同类问题迁移

矩阵链乘法是区间DP的思想原点。很多看似不同的问题，只要满足“大区间由小区间合并而来”的结构，都可以套用这套方法论。典型的有石子合并（相邻堆合并最小代价）、最优三角剖分（多边形划分三角形的最小权重和）、括号序列最小区间补全等。

以石子合并为例，状态dp[i][j]表示合并第i堆到第j堆石子的最小代价，转移枚举最后一组合并的分界点k，dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i,j))，和矩阵链乘法的框架几乎完全一样，只是把合并代价p[i-1]*p[k]*p[j]换成了区间和sum(i,j)。你只要完整理解一个，就能快速迁移到另一个。

8.2 为什么实际工程里还会用到这个模型

矩阵链乘法本身在图形学、物理模拟里确实会出现——比如一个模型要连续乘以旋转矩阵、缩放矩阵、平移矩阵，排列这些变换的顺序会影响计算量。在AI框架的算子优化里，虽然不会直接用这个经典DP决定整个计算图（还要考虑显存占用、中间结果复用、并行度），但“把连续线性层合并计算时如何安排形状”的底层思维，和矩阵链乘法是一脉相承的。懂得这套推导逻辑的人，看计算图优化会顺眼很多。

我个人学这道题的体会是：区间DP入门阶段最值得投入时间的地方，不是背转移方程，而是亲手把三重循环的填表顺序、“为什么短区间要先算”、“边界为什么这样写”全部用调试器或打印日志验证一遍。把这些基本功打扎实了，后面遇到再复杂的区间DP变形题，你都能迅速回到这个模型上来。几个小练习可以做：把代码换成记录方案并输出完整括号串；自己随机生成p数组，对比Knuth优化和基础版的结果；再试试把答案改成计算最大代价，体会一下为什么这种“最大最小换个方向”的题照样能用同一套框架。