1. 一个手算的例子括号位置不同乘法次数差了9倍1.1 三个矩阵两种括号两种代价矩阵连乘问题用一句话讲就是给一串连乘的矩阵怎么加括号让计算机少做点乘法。很多初学算法的人第一次看到这个问题都觉得有点莫名其妙——乘法不就是乘法吗先算哪两个难道还有区别我当年在《计算理论与算法分析设计》这门课里第一次看到矩阵连乘问题也是这么想的。直到我手算了一个小例子才意识到这个问题的水比想象中深得多。假设有三个矩阵A1 是 10 × 20 的矩阵A2 是 20 × 50 的矩阵A3 是 50 × 1 的矩阵连乘 A1 × A2 × A3规则只有两个矩阵乘法满足结合律矩阵乘法不满足交换律。所以本质上只有两种加括号方式方式一(A1 × A2) × A3方式二A1 × (A2 × A3)先算方式一。A1 乘 A2两个矩阵的尺寸是 10×20 和 20×50得到的中间结果是 10×50。做这一次乘法需要多少次标量乘法10 × 20 × 50 10000 次。得到中间结果后再乘 A350×1中间结果是 10×50A3 是 50×1做这一次乘法需要10 × 50 × 1 1000 次。加起来方式一总共需要 11000 次标量乘法。再算方式二。先把 A2 和 A3 相乘尺寸是 20×50 和 50×1中间结果是 20×1。这一次需要的乘法次数是20 × 50 × 1 1000 次。然后 A110×20乘上中间结果20×1需要10 × 20 × 1 200 次。加起来方式二总共只要 1200 次标量乘法。11000 对 1200差了将近 9 倍。同一个数学表达式只是因为括号位置不同计算量就从一万多降到了一千多。更关键的是这两种方式最终得到的矩阵完全一样都是 10×1 的矩阵。这个例子直接把矩阵连乘求最优加括号顺序这个问题的意义敲死了括号没加对计算量白白翻十倍。1.2 把问题严格化以及计算量到底指什么前面用的是最简单的三矩阵例子现在把问题严格化。给定 n 个矩阵 A1, A2, ..., An每个矩阵 Ai 的规模是 p[i-1] × p[i]也就是说相邻矩阵的维度是兼容的整个链可以连乘。要找到一种加括号方式使得完成整个连乘所需要的标量乘法次数最少。这里的标量乘法指的是矩阵乘法中内层循环里那一次乘法操作。比如 Am×p乘 Bp×n结果 C 是 m×n一共要做 m × p × n 次标量乘法这个数值和一次乘法的开销直接正相关。实际计算机里浮点乘法和浮点加法的开销不完全一样但做算法分析的建模阶段用标量乘法次数作为衡量标准已经足够接近真实情况而且推导和比较都很方便。于是问题的输入就变成了一个长度为 n1 的数组 p而不是 n 个完整的矩阵对象。矩阵本身的元素值完全不用考虑我们关心的是它们首尾相接的尺寸序列。这个维度数组驱动一切的视角非常重要很多后面要写的代码、要证的递推式都是围绕 p 数组展开的。要注意一个容易混淆的地方矩阵连乘问题的最优解关注的是运算次数不是存储空间。中间结果矩阵当然也会占内存但这在基础版问题里不是优化目标。等到实际工程里把 GPU 显存、访存带宽算进来这个问题就会变得更复杂后面我会单独提到。2. 暴力为什么不行方案数量按卡特兰数爆炸2.1 加括号方案的计数递推如果不知道动态规划第一反应肯定是暴力枚举所有加括号方式逐个算出代价取最小。这个思路本身没错错在方案数量增长太快。n 个矩阵连乘一共有多少种加括号方式设 P(n) 表示 n 个矩阵的加括号方案数。最外层总有一个分割点把链切成两部分左边 i 个矩阵右边 n-i 个矩阵再分别对两边加括号。于是递推关系是P(n) Σ(k1, n-1) P(k) × P(n-k)其中 P(1) 1。这个递推式和卡特兰数的递推一模一样算出来P(1) 1P(2) 1P(3) 2P(4) 5P(5) 14P(6) 42P(10) 16796P(15) 2674440P(20) 6564120420到了 n20方案数已经超过 65 亿。就算一台机器每秒能评估一亿种方案也要一分多钟n 到 30方案数超过 3.8 × 10^16暴力枚举在工程上没有任何希望。这里值得多讲一句很多人记不住卡特兰数的通项公式其实也不需要死记。你只要能从乘法结合律的角度写出上面这个递推就能直观感受到每多一个矩阵括号方案数增加得更猛。这个递推在面试里也是一个经典考点面试官有时候不直接考矩阵连乘而是问n 个矩阵连乘有多少种加括号方式本质考的就是这个数列。2.2 从暴力到动态规划重叠子问题的出现暴力枚举慢不只是因为方案总数爆炸更本质的原因是大量重复计算。比如在 n5 的情况里无论是哪一层的分割子链 A2·A3·A4 的最小代价会被反复计算很多次。递归树展开之后相同区间会出现在不同分支里每次都要重新算一遍。这种结构就是教科书上说的重叠子问题也是动态规划能切入的根本前提。我当时在课堂上第一次理解到这一层时觉得整个算法设计思维发生了变化不需要追求把所有方案枚举出来只需要保证每个子区间只认真算一次后面直接查表。于是这个问题就从组合枚举问题变成了填一张二维表的问题。很多人会有个疑问为什么矩阵连乘能用区间 DP而旅行商这种问题就不太好用答案就在于子问题的结构。矩阵连乘的一个子链总是原链的连续一段任意分割后产生的两个子链仍然是连续区间区间之间是并列关系。而很多其他组合优化问题的拆分会产生交叉依赖没法用区间这样干净地切分。这种切一刀变两段、两段独立求解的模式是区间 DP 的典型特征。3. 动态规划建模三件套状态、转移方程、填表顺序3.1 状态 m[i][j] 为什么选择区间而不是前缀很多算法题里常见的 DP 状态是前 i 个东西怎么怎么样比如背包问题的 dp[i][w]。但矩阵连乘问题不一样它不能简单用前缀来做状态。原因在于当你决定整个矩阵链从第 k 个矩阵后面断开时右半部分是 Ak1 到 An它不是一个以 1 开头的前缀而是一个从中间开始的区间。也就是说一个问题的最优策略天然会把原链切成两段而且两段都可能是中间段。反过来如果只用前缀状态你就必须枚举右段的终点而右段的子问题又会切成更细的区间最终你还是绕不开任意连续区间这个形态。所以状态的定义只能是m[i][j] 表示计算 Ai 到 Aj 这段连续子链所需的最少标量乘法次数其中 1 ≤ i ≤ j ≤ n。一个特殊情况是 i j也就是子链只有一个矩阵不需要做任何乘法所以 m[i][i] 0。这个初始化是整个 DP 的基石几乎所有后续计算都建立在这条对角线之上。你可以把 m[i][j] 理解成一个关于区间的记忆单元。整个问题最终想要的 m[1][n] 就存放在这张二维表的右上角。表里面每一格只要算一次之后谁需要谁直接取这就是动态规划相对暴力递归的优势。3.2 转移方程的分割点思想现在看 m[i][j] 怎么从更小的子问题递推出来。假设最终在 k 处断开i ≤ k j即先算 Ai 到 Ak再算 Ak1 到 Aj最后把两个结果矩阵乘起来。总代价就有三部分左边子链的代价m[i][k]右边子链的代价m[k1][j]最后那次乘法本身的代价Ai..k 的结果矩阵和 Ak1..j 的结果矩阵相乘需要的标量乘法次数。第三部分怎么算Ai 到 Ak 连乘的结果矩阵规模是 p[i-1] × p[k]Ak1 到 Aj 连乘的结果矩阵规模是 p[k] × p[j]两部分相乘需要的标量乘法次数是p[i-1] × p[k] × p[j]于是对于一个固定的分割点 kcost(i, j, k) m[i][k] m[k1][j] p[i-1] × p[k] × p[j]最优的就是遍历所有可能的 k取最小值m[i][j] min{ m[i][k] m[k1][j] p[i-1] × p[k] × p[j] }其中 i ≤ k j这个转移方程看起来简单但有三点必须反复理解第一k 是分割点而不是矩阵的下标。很多人把 k 理解成第几个矩阵处断开实际上 k 表示的是断在 Ak 和 Ak1 之间。所以 k 的取值范围是 i 到 j-1一共 j-i 个候选。第二最后一项里的三个 p 下标不会随着具体矩阵元素变化它只取决于子链两端和分割点。这个形式非常整齐写代码时只要照着 p[i-1]、p[k]、p[j] 三个位置取值就不会乱。第三这个转移方程天然假设了最优子结构。也就是全局最优解一定包含着子链的最优解。如果左边子链存在比 m[i][k] 更优的策略那么全局方案也能替换成更优策略而不会影响右边于是全局就不是最优了矛盾。这个反证逻辑是动态规划正确性的标准证明框架面试时讲清楚比单纯背代码有用得多。3.3 为什么必须按区间长度从小到大填表状态和转移方程都清楚了接下来一个非常容易踩的坑就是填表顺序。m[i][j] 依赖 m[i][k] 和 m[k1][j]。观察这两个子问题的区间长度m[i][k] 的长度是 k - i 1m[k1][j] 的长度是 j - k。由于 k 在 i 和 j 之间这两个长度都严格小于 j - i 1。也就是说一个区间的最优解只依赖更短区间的最优解绝不依赖更长区间。这给了我们一个天然的填表策略外层循环枚举区间长度 l从 2 到 n内层枚举所有长度为 l 的区间 [i, j]再内层枚举分割点 k。为什么不能换成外层枚举 i、内层枚举 j这种常见套路因为当你计算 m[1][n] 时你需要 m[2][n] 这个值。如果你按 i 从 1 到 n 的顺序填表算到 i1、jn 的时候m[2][n] 还没被算过因为 i2 这层还没轮到。这就是经典的依赖了尚未计算的表项。而按区间长度从小到大填任何需要的子区间都比当前区间短早已在之前的轮次中填好了。这个填表顺序是区间 DP 类问题的通用法则。不只是矩阵连乘石头合并、回文串划分、多边形剖分只要状态是连续区间一律按区间长度从短到长来遍历。把这个规律记在心里能帮你省下大量调试时间。4. 完整代码实现与下标暗坑4.1 一份带注释的 Python 写法先给一份最经典的 Python 实现逻辑严谨适合课程作业和复习def matrix_chain_order(p): n len(p) - 1 # 矩阵个数 # m[i][j] 表示 Ai..Aj 的最小乘法次数表大小 (n1)x(n1) m [[0] * (n 1) for _ in range(n 1)] # s[i][j] 记录让 m[i][j] 取最小值的分割点 k s [[0] * (n 1) for _ in range(n 1)] # l 是区间长度从 2 开始因为长度为 1 的区间代价已经是 0 for l in range(2, n 1): for i in range(1, n - l 2): j i l - 1 m[i][j] float(inf) for k in range(i, j): cost m[i][k] m[k 1][j] p[i - 1] * p[k] * p[j] if cost m[i][j]: m[i][j] cost s[i][j] k return m, s这段代码有个细节range(1, n - l 2)很多人第一次看不懂。它的作用是保证 j i l - 1 不超过 n。举个例子n5l3 时 i 最大是 3j 最大是 5i 的取值范围是 1 到 3。n-l2 5-32 4range(1,4) 正好是 1,2,3。可以这么记忆区间右端点 j 必须 ≤ n所以 i ≤ n - l 1循环里写成 range(1, n - l 2) 是因为 range 右边是开区间。调用方式p [10, 20, 50, 1] m, s matrix_chain_order(p) print(m[1][3]) # 12004.2 p 数组下标映射p[i-1] × p[k] × p[j] 逐项拆解我见过太多人在这一步翻车所以要专门拆一下下标逻辑。p 数组长度为 n1矩阵 Ai 的尺寸是 p[i-1] × p[i]。比如 p [10, 20, 50, 1]A1 是 p[0]×p[1]即 10×20A2 是 p[1]×p[2]即 20×50A3 是 p[2]×p[3]即 50×1。现在计算 m[i][j]也就是 Ai 到 Aj 连乘。最后一部把左边和右边乘起来需要怎样的乘法次数左边 Ai 到 Ak 连乘的结果矩阵是 p[i-1] × p[k]右边 Ak1 到 Aj 连乘的结果矩阵是 p[k] × p[j]。因为矩阵维度是首尾相接的中间的公共维度就是 p[k]。所以最后一步的乘法次数是p[i-1] × p[k] × p[j]这里三个下标的规律其实很好记左端点减一分割点右端点。写代码时先把这三个变量打出来对一遍再放进乘法里left_dim p[i - 1] mid_dim p[k] right_dim p[j] cost m[i][k] m[k 1][j] left_dim * mid_dim * right_dim把变量名写得清清楚楚比一行写完整条表达式更能减少低级错误。实际开发中我也会建议别人这样写虽然看起来啰嗦但可读性和可维护性都更好。4.3 C 还是 Python课程实现的一点个人建议如果是课程作业或者面试手写我个人更推荐先用 Python 把逻辑跑通因为数组初始化和循环边界写起来更省心。如果题目要求提供 C 版本核心代码也很短#include vector #include algorithm using namespace std; const int INF 1e9; vectorvectorint matrixChainOrder(const vectorint p) { int n p.size() - 1; vectorvectorint m(n 1, vectorint(n 1, 0)); vectorvectorint s(n 1, vectorint(n 1, 0)); for (int l 2; l n; l) { for (int i 1; i n - l 1; i) { int j i l - 1; m[i][j] INF; for (int k i; k j; k) { int cost m[i][k] m[k 1][j] p[i - 1] * p[k] * p[j]; if (cost m[i][j]) { m[i][j] cost; s[i][j] k; } } } } return m; }需要注意 C 中int可能溢出。当矩阵维度是几千级别、n 上百时乘积会超过 2^31。正规做法是用long long装所有 DP 值。这一点在课程里不常考但在真实工程或面试手写时会是个加分项。5. 把最优方案找回来s 表与递归输出加括号5.1 分割点记录表到底在记录什么只求出最小乘法次数还不够很多时候问题会要求请输出最优的加括号方案。这时候就要用到 s 表。s[i][j] 记录的就是在使 m[i][j] 取得最小值的所有分割点 k 中我们采用的是哪一个。换句话说s[i][j] 告诉你区间 [i, j] 的最优解法是在哪个位置断开的。这个表的结构和 m 表一样。对角线不需要填每个非对角线格子填一个介于 i 和 j-1 之间的整数。例如前面三矩阵例子 p [10, 20, 50, 1]算完之后s[1][2] 1表示 A1·A2 的最优断点是 k1s[2][3] 2表示 A2·A3 的最优断点是 k2s[1][3] 1表示 A1·A2·A3 的整体最优断点是 k1。5.2 递归回溯把一张表翻译成括号表达式有了 s 表输出最优括号就变成了一次递归遍历def print_parens(s, i, j): if i j: return fA{i} k s[i][j] left print_parens(s, i, k) right print_parens(s, k 1, j) return f({left}{right})按 s[1][3] 1先递归左边 [1,1]输出 A1再递归右边 [2,3]而 s[2][3] 2右边继续递归得到 (A2A3)。拼接结果是 (A1(A2A3))。这里有个容易误解的小地方print_parens(s, i, k)里的 k 是上一层选好的分割点而递归进入 [i, k] 之后会自动读取 s[i][k] 作为新的分割点。所以整个过程不需要再传别的参数一张 s 表足够。如果你担心递归深度n 一般不会超过几百递归深度和矩阵个数同级正常没问题。但如果 n 非常大或者环境限制递归深度也可以用栈模拟递归的输出顺序不过课程场景通常不需要。5.3 怎么验证结果手动填表对照法我教过的不少学生在做完这个题之后不知道自己的结果对不对。这里给一个非常实用的验证方法拿一个四矩阵的例子手动把 m 表填一遍。假设有一个四矩阵链p [5, 4, 6, 2, 7]也就是 A1:5×4A2:4×6A3:6×2A4:2×7。长度 2m[1][2] 5×4×6 120m[2][3] 4×6×2 48m[3][4] 6×2×7 84长度 3m[1][3] min( m[1][1] m[2][3] 5×4×2, m[1][2] m[3][3] 5×6×2 )k10 48 40 88k2120 0 60 180所以 m[1][3] 88s[1][3] 1同理 m[2][4]k20 84 4×6×7 252k348 0 4×2×7 104所以 m[2][4] 104s[2][4] 3长度 4m[1][4] min(k10 m[2][4] 5×4×7 104 140 244k2m[1][2] m[3][4] 5×6×7 120 84 210 414k3m[1][3] 0 5×2×7 88 70 158)结果是 158s[1][4] 3。做完这步再用代码跑一遍m[1][4] 应该等于 158输出的括号方案是 ((A1(A2A3))A4) 或者等价形式。能对上就说明状态定义、转移方程和代码实现都正确。这个手算对照的习惯到今天我做复杂算法题还在用。6. 复杂度分析与常见坑位盘点6.1 时间空间复杂度以及是否可以优化矩阵连乘问题的时间复杂度是 O(n³)空间复杂度是 O(n²)。这个复杂度是怎么来的三重循环外层枚举区间长度 l最多 n 种中层枚举区间起点 i最多 n 种内层枚举分割点 k最多 n 种。乘法次数就是 O(n³)。空间上需要 m 表和 s 表每张都是 n×n 的规模所以 O(n²)。O(n³) 在算法题里属于中等偏重的复杂度。n 到 100 很轻松n 到 1000 就有点压力了n 到 5000 基本不可行。所以这个基础版算法适合小规模精确求解。如果需要优化通常不是优化 DP 本身而是利用问题的特殊结构。有一个经典的加速方向如果维度序列满足某种单调性转移的最优决策点 k 也具有单调性可以用四边形不等式优化把复杂度降到 O(n²)。不过这个优化需要性质分析且实现细节多课程阶段很少有人深挖知道有这条路就行。6.2 我见过最容易翻车的三个位置第一个翻车点前面已经说过就是外层循环顺序写错。把for l写成for i结果 m[2][n] 还没算就拿来用程序输出的都是诡异的大值。排查方法很简单先做小规模手算对照或者打印 m 表的填充顺序看有没有使用未计算的格子。第二个翻车点是初始化。很多人把 m[i][i] 初始化为某个大数而不是 0。这样计算所有长度大于 1 的区间时枚举到 ki 或者 kj-1 会带上一个错误的初始值。记住单个矩阵不需要乘法代价一定是 0不用犹豫。第三个翻车点是边界。比如循环是range(i, j)分割点 k 的范围如果不小心写成了range(i, j1)就会访问 m[j1][j] 或者越界。k 的最大值是 j-1因为右边子链至少要有一个矩阵。写代码时把 k 的取值范围和右边至少还有一个矩阵这句话对应起来就不容易错。我统计过给学生改作业时的错误分布大概一半是填表顺序错三成是下标或者初值错剩下的是输出方案时递归边界写错。这些坑都是看似简单、一写就废的典型。6.3 变种问题输出方案、统计最优方案数、断链表示矩阵连乘还有一些常见的变体课程和面试都可能出现。第一个变种是要求输出所有最优方案。标准做法是在计算 m[i][j] 时用一个小数组把所有取得最小值的 k 都记录下来输出时再逐一递归。注意可能遇到指数级方案的情况n 稍微大一点就很多所以题目一般只要求任意输出一种或者统计方案数。第二个变种是统计最优加括号方案的数量。思路不算复杂用一个 dp_cnt 表长度 1 时方案数为 1计算长度大于 1 的区间时求所有 k 中满足 cost m[i][j] 的分割点把左边方案数乘以右边方案数累加起来。注意这里不是简单的总方案数而是达到最小代价的方案数所以必须同时参照 m 表判断。第三个变种是把加括号方案理解成一棵二叉树。每个区间 [i, j] 是一棵子树分割点 k 是根。这棵树的中序遍历就是矩阵下标 1 到 n而后缀遍历或前序遍历则对应某种计算顺序。理解这一点之后矩阵连乘问题和最优二叉搜索树凸多边形最优三角剖分这几个经典 DP 问题就串起来了它们都是同一类区间划分问题的不同外壳。7. 从教学题到工程问题矩阵连乘的思想在哪些地方继续发光7.1 矩阵链乘的运算顺序问题在真实场景里无处不在矩阵连乘在算法课里是一道经典习题但它绝不是纸上谈兵。只要你的程序里出现多个矩阵连续相乘就存在选择最优运算顺序的问题。我举一个很朴素的生产场景。某项目里需要计算 A × B × C × D其中 A 是 200×300B 是 300×500C 是 500×10D 是 10×800。如果按照从左到右的顺序算最开始的中间矩阵就是 200×500后面还有 200×10 等中间结果整体计算量明显偏高。用矩阵连乘算法算一遍之后发现优先算 B×C 能显著减少中间矩阵的规模计算量能下降一个数量级。类似的场景在数值计算库、图形学变换、深度学习模型推理中都存在。比如深度学习里连续做若干次矩阵乘中间张量的形状各不相同选择什么样的结合顺序直接影响 FLOPs 和显存占用。虽然是神经网络的框架层在做这类优化但背后的思想仍然是矩阵连乘问题的区间 DP 思路。7.2 当 n 变大时从精确转近似但区间 DP 思想不变前面说过 O(n³) 的限制。真实场景中如果矩阵链很长精确求解会不可接受这时就要退而求其次用贪心、随机搜索、启发式算法去找一个足够好的加括号方案。比如可以每次贪心地选择当前乘法代价最小的两个相邻矩阵先乘这种方法不能保证全局最优但速度很快而且大部分情况下结果相当可用。工程上还有一个思路是划分治之把大链切成长度相近的若干段每段用精确 DP 求解段与段之间再按一定顺序合并。这其实还是在做先分段再整体的区间思想。但不管用什么启发式区间 DP 的 m 表和 s 表仍然是分析这类问题最好的出发点。因为你至少要能评估一种加括号方案的成本才能做优劣比较而矩阵连乘 DP 教你的正是给定区间求最小成本的精确计算方法。从这个意义上说课程里的 O(n³) 算法不是终点是后续一切方案的基础设施。7.3 向相关经典 DP 延伸同一个骨架不同的外壳矩阵连乘问题掌握之后有几个问题可以顺路一起学因为它们本质是同一套区间 DP 框架凸多边形的最优三角剖分状态同样是区间转移同样是枚举分割点只是代价函数从矩阵乘法次数换成了三角形权值之和。石子合并问题在一条线上合并相邻石子堆每次合并的代价是两堆重量之和求最小总代价。状态是区间 [i, j]转移是枚举最后合并的分割点几乎和矩阵连乘一模一样。最优二叉搜索树也是区间上的动态规划但它的代价计算方式带上了访问概率转移方程会稍微复杂一些不过骨架逻辑相通。把这几个题放在一起对比学习比单独刷一个题效率高得多。你很快会发现区间 DP 的核心三件事——区间状态、分割点枚举、按长度填充——在每一道题里都成立区别只是代价函数的形态不同。说回实践层面的体会。矩阵连乘是我在算法课程里刷过最多次的经典题之一每次重新手写都会对状态设计和填表顺序多一层理解。对初学动态规划的人我强烈建议不要只盯着代码敲一定亲手画一张 m 表体会每个格子是怎么依赖其他格子的。动态规划不是一个背模板去套的知识点而是把重复计算变成查表的思维方式。矩阵连乘问题恰恰是最适合建立这种思维的第一块跳板。