区间动态规划里矩阵链乘法是一道绕不过去的入门题。题目短到一句话可以说清楚给一串矩阵每个的尺寸都给定乘法顺序随便加括号问最少要做多少次标量乘法。但就是这道题几乎把区间DP的核心套路全占齐了状态怎么设、区间怎么枚举、决策点怎么找、方案怎么回溯、复杂度怎么优化。很多人被“矩阵链”三个字吓住以为要跟矩阵运算死磕其实本质就是“在一个连续区间里切一刀左右各自最优再把两个子问题拼起来”。今天就把这道题从头到尾拆一遍把递推公式、两种写法和那些容易踩的坑一次说清。适合谁看刚学会动态规划、想系统接触区间DP的读者准备笔试面试想快速掌握经典模型的读者以及已经会基本写法、想进一步了解四边形不等式优化的读者。矩阵链乘法是少有的“从入门到进阶一条线”的题从最朴素的 O(n^3) 到 O(n^2) 优化都能在一道题里讲明白非常值得彻底吃透。1. 先说结论矩阵链乘法到底在求什么1.1 问题本身不长但信息量不小假设手头有 n 个矩阵排成一串A1、A2、……、An。每个矩阵的行列数都是已知的并且相邻矩阵满足乘法条件也就是前一个矩阵的列数等于后一个矩阵的行数。现在要把这一串矩阵全部乘到一起要求最终得到一个矩阵。因为矩阵乘法满足结合律所以括号怎么加都能得到同一个结果矩阵但不同括号顺序下中间需要做的标量乘法次数差别非常大。注意这里说的“标量乘法次数”不是矩阵元素个数而是数字相乘的次数。比如两个矩阵 X 是 m×nY 是 n×p那么 X×Y 要做的标量乘法次数是 m×n×p。这个代价函数是整个问题的关键后面递推公式里的每一项都是从它来的。“求最小代价”就是题目要求的答案。最直接的想法是枚举所有加括号方案看哪种代价最小。但括号方案数量是卡特兰数增长非常快n10 时已经上万种n 稍微大一点就彻底没法枚举了。动态规划就是用来做这件事的。1.2 顺序不同代价能差出好几倍举个例子三个矩阵A110×30A230×5A35×60如果先算 A1×A2得到一个 10×5 的中间矩阵再乘 A3。第一步代价是 10×30×51500第二步代价是 10×5×603000总代价 4500。如果先算 A2×A3得到一个 30×60 的中间矩阵再乘 A1。第一步代价是 30×5×609000第二步代价是 10×30×6018000总代价 27000。同一个表达式只是换了一下括号位置代价差了整整 6 倍。矩阵规模再大一点、矩阵个数再多一点差距会变成指数级别。这也是为什么不能随便从左往右算需要一个靠谱的算法来找最优顺序。1.3 这道题为什么值得花时间矩阵链乘法的价值在于它是区间 DP 这个类型的“课代表”。只要你把这道题的转移方程写熟后面遇到石子合并、最优二叉搜索树、多边形三角剖分都会发现有极其相似的骨架都是在一个连续区间上枚举一个分割点把区间分成左右两段用两个子问题的答案拼出当前区间答案。如果只把它当一道“矩阵题”来做那就浪费了。它真正训练的是你识别“区间模型”、构造“子问题拼接公式”的能力这对很多 DP 题的迁移都很有帮助。2. 状态设计与递推公式区间DP的关键2.1 从“最后一次乘法”切进去动态规划最怕没有切入角度。矩阵链这道题有一个特别自然的切入口不管括号怎么加整条链最后一步一定是把某两个矩阵乘到一起。也就是说存在一个分界点 k使得最终结果是“左边 A[i..k] 部分相乘的结果”乘上“右边 A[k1..j] 部分相乘的结果”。这个视角非常关键因为它把一个大问题拆成了两个同性质的子问题左半边是一个矩阵链乘法右半边也是一个矩阵链乘法。而且左右两边都是原数组里连续的一段这正是“区间 DP”这个名字的由来。如果左右两半各自都用了最优方案那么当前这个分割点下整体代价就是左半最优值加右半最优值再加上最后那一次乘法的代价。因为最后那一次乘法的尺寸是确定的所以最优解一定可以分解成两个子问题的最优解。这就是“最优子结构”。2.2 状态定义dp[i][j] 表示一个区间用 dp[i][j] 表示从第 i 个矩阵乘到第 j 个矩阵的最小标量乘法次数其中 i 小于等于 j。比如 dp[2][4] 表示 A2、A3、A4 这三段矩阵链的最小代价。边界条件很简单单个矩阵不需要任何乘法所以 dp[i][i]0。这里要特别习惯“下标偏移”。假设有一个维度数组 p长度为 n1矩阵 Ai 的尺寸是 p[i-1]×p[i]。也就是说 p[0] 是第一个矩阵的行数p[i] 是第 i 个矩阵的列数也是第 i1 个矩阵的行数。这个偏移是很多初学者一开始觉得别扭的地方但代码写多以后会发现这样设计能让递推公式非常规整。拿四个矩阵举例p[0..4] 对应A1p[0]×p[1]A2p[1]×p[2]A3p[2]×p[3]A4p[3]×p[4]最终答案 dp[1][n] 就是所有矩阵乘完的最小代价。2.3 递推公式枚举分割点 k把问题拆成“最后一次乘法在 k 处发生”可以得到转移方程dp[i][j] min( dp[i][k] dp[k1][j] p[i-1] * p[k] * p[j] )其中 i k j。解释一下每一项的含义。dp[i][k] 是左半链 A[i..k] 的最小代价结果矩阵的尺寸是 p[i-1]×p[k]。dp[k1][j] 是右半链 A[k1..j] 的最小代价结果矩阵的尺寸是 p[k]×p[j]。两个结果矩阵相乘时左矩阵行数是 p[i-1]中间公共维度是 p[k]右矩阵列数是 p[j]所以最后那一次乘法代价是 p[i-1]×p[k]×p[j]。为什么是 p[k]不是 p[k1] 之类的因为左半链最后一步得到的矩阵列数取决于最后一个矩阵 Ak 的列数也就是 p[k]。而右半链的第一个矩阵是 A[k1]它的行数恰好也是 p[k]两者匹配。这个公共维度就是连接左右两边的“接口”。所以要得到 dp[i][j]就需要遍历所有可能的 k把每种分割方式算出来的代价取最小值。这个 k 就是决策点。2.4 为什么不能贪心有些读者看到这里会想既然每次乘法代价是 p[i-1]×p[k]×p[j]那是不是每次尽量选“最容易”的相邻乘法就行比如合并两个尺寸相近的、代价最小的答案是不行因为局部最优会牺牲全局结构。前面三矩阵的例子中先合并 A1×A21500反而比先合并 A2×A39000好看起来“选代价小的合并”似乎有效。但只要矩阵更多这个策略很快失效。最典型的反例是当前一个局部合并代价小但会让后面的大矩阵乘法尺寸变得非常糟糕积少成多总量反而更大。动态规划之所以可靠是因为它不赌“哪一步好”而是把所有可能的分割点都算一遍在全局所有方案里取最优。复杂度高一些但正确性有保证。这也就是为什么这道题不能用简单贪心或者只挑固定方向扫描的原因。3. 从公式到代码迭代版与记忆化搜索3.1 按区间长度推进的迭代写法区间 DP 最常见的写法是“区间长度从小到大”循环。先算所有长度为 1 的区间再算长度为 2 的区间依次递推上去。这样在计算长度较大的区间时它依赖的左半区间和右半区间都已经算完了。先给出完整的 C 代码再逐段解释。#include bits/stdc.h using namespace std; const long long INF 4e18; int main() { int n; cin n; vectorlong long p(n 1); for (int i 0; i n; i) { cin p[i]; } vectorvectorlong long dp(n 1, vectorlong long(n 1, 0)); vectorvectorint s(n 1, vectorint(n 1, 0)); for (int len 2; len n; len) { for (int i 1; i len - 1 n; i) { int j i len - 1; dp[i][j] INF; for (int k i; k j; k) { long long 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; } } } } cout dp[1][n] endl; return 0; }外层循环len是区间长度从 2 开始因为长度为 1 时 dp[i][i]0不需要处理。第二层循环枚举区间起点 i终点 j 用i len - 1算出来。第三层循环枚举分割点 k。为什么必须先枚举长度而不是直接枚举 i、j因为 dp[i][j] 依赖的 dp[i][k] 和 dp[k1][j] 长度都小于 j-i1。如果不按长度从小到大而只是简单地用 i 从后往前、j 从前往后可能用到尚未计算的位置结果全错。这是区间 DP 最容易犯的一个错误。3.2 记忆化搜索版本适合快速验证思路迭代写法虽然高效但有时候第一步写不出来尤其当一个递归公式比较复杂时。这时候可以用记忆化搜索直接按递归定义写靠 memo 数组避免重复计算。vectorvectorlong long memo(n 1, vectorlong long(n 1, -1)); long long dfs(int i, int j) { if (i j) return 0; if (memo[i][j] ! -1) return memo[i][j]; long long res INF; for (int k i; k j; k) { res min(res, dfs(i, k) dfs(k 1, j) p[i - 1] * p[k] * p[j]); } return memo[i][j] res; }这个版本写起来非常直观基本就是把数学公式翻译成代码。调用dfs(1, n)就能得到答案。它的缺点是递归调用有一定开销而且当 n 很大时递归深度可能达到 n有爆栈风险。解法验证、笔试题里用记忆化搜索完全没问题追求极致性能或者 n 接近上千时用迭代版本更稳妥。还有一个小细节memo 初始化成 -1是因为合法结果有可能是 0不能用 0 来代表“没算过”。3.3 如何输出最优括号方案只输出最小代价还不够很多题目会要求你输出一种加括号的方式。这时候需要用一个额外的决策数组s[i][j]记录 dp[i][j] 取得最小值时用的 k 值。上面迭代代码里已经顺手维护好了。递归打印函数void print(int i, int j) { if (i j) { cout A i; return; } cout (; print(i, s[i][j]); cout x ; print(s[i][j] 1, j); cout ); }思路很简单区间 [i,j] 的最优分割点是 s[i][j]那就在这个位置把输出分成左右两段分别递归打印中间用“x”连接外面加一对括号。如果有多个最优方案这个函数输出的是 s[i][j] 记录的第一个最优值也就是遍历 k 时第一次遇到最小值的那个方案。打印出来的结果就是类似((A1 x A2) x (A3 x A4))这样的完全括号化表达式。平时做题时能用这个函数验证自己的方案是不是合理非常顺手。4. 复杂度分析与避坑清单4.1 时间与空间复杂度最基本的迭代写法是三层循环外层区间长度内层区间起点最内层分割点。每次分割点都要计算一个dp[i][k] dp[k1][j] cost所以总时间复杂度是 O(n^3)。空间上要存 dp 数组和可选的 s 数组都是 O(n^2)。很多人对 O(n^3) 没有直观概念。n100 时内层总计算量大概是 16 万次左右完全没问题n500 时达到约 2000 万次也还行n1000 时就要上亿了C 还能勉强跑Python 就会很吃力。如果遇到 n5000 甚至更大的数据就必须考虑状态压缩或者四边形不等式优化。这里要特别提醒代价计算中p[i-1] * p[k] * p[j]是三个数相乘维度值可能很大。如果开 intn 稍大一些或者维度给到上千就可能溢出。稳妥起见全部用long long。4.2 最容易踩的索引坑矩阵链这道题的“坑”几乎都集中在索引上。我第一次完整写这个代码的时候就在第三层循环里把p[i-1] * p[k] * p[j]写成了p[i] * p[k] * p[j]结果答案怎么都不对后来拿纸笔推了一遍尺寸才改过来。核心点在于dp[i][j] 表示的是第 i 个到第 j 个矩阵所以左半部分结果的矩阵是 A[i..k]它的行数取决于第一个矩阵 Ai 的行数也就是 p[i-1]列数取决于最后一个矩阵 Ak 的列数也就是 p[k]。同样右半结果的列数取决于最后一个矩阵 Aj 的列数也就是 p[j]。三个 p 下标分别是i-1、k、j。有一个记忆技巧把 p 数组想成相邻矩阵之间的“边界宽度”。A1 的左边是 p[0]A1 和 A2 之间是 p[1]A2 和 A3 之间是 p[2]以此类推。合并 [i,j] 区间时最左边是 p[i-1]中间切在 p[k]最右边是 p[j]。这样写起来就不容易错。另外k 的枚举范围是i k j不是i k j也不是k j。如果写成k jdp[j1][j] 是一个不存在的空区间数组越界不说逻辑也完全不对。4.3 初始化、边界和溢出问题dp 数组可以初始化为 0然后单独设置 dp[i][i]0因为非对角线位置会被后续的 min 操作覆盖。但为了安全很多人在循环前把 dp 全部设为 INF再对 ij 的位置设为 0。两种方式都行只要保证计算 dp[i][j] 时不会用到未初始化的垃圾值。边界情况也要考虑。如果 n1不需要乘法答案是 0。如果只有两个矩阵len2 的循环会直接处理k 只有一个取值答案就是 p[0]*p[1]*p[2]。输入维度数组时要注意p 的长度是 n1矩阵个数 n 必须至少为 1否则没有意义。long long 的上限大约是 9e18INF 可以设置成4e18这样的安全值。实际最大代价最坏情况下是 O(n) 个乘法项相乘n 和维度都在 1000 以内时不会接近这个上限。但要是维度给到 1e5 级别即使 long long 也可能溢出那就需要提前判断或者用 Python 的大整数。4.4 常见错误速查表我把平时写这道题容易犯的错整理成了一张表方便对照排查。错误现象可能原因dp[1][n] 一直是 INF没有正确先处理长度 1或者 k 循环写成 k j结果偏大合并代价下标写错比如用了 p[i] 代替 p[i-1]或者用了 p[j1] 代替 p[j]输出括号时递归死循环s[i][j] 为 0 或越界没有维护好决策数组小数据对大数据结果怪异int 溢出改成 long long两层 i、j 循环得到错误答案没有按区间长度从小到大枚举依赖的子区间尚未计算矩阵维度对不上p 数组读入长度少了 1或者矩阵 Ai 的尺寸定义反了5. 进阶Knuth优化把复杂度压到 O(n^2)5.1 四边形不等式到底在说什么很多区间 DP 满足一个叫“四边形不等式”的性质直观理解就是代价函数不能太“扭曲”当区间变大时边界变化带来的增量是规律的。对于矩阵链乘法来说这个条件通常是成立的因此存在一个非常著名的优化——Knuth 优化。Knuth 优化的结论在代码层面试起来就是一句如果 dp[i][j] 的最优分割点是 s[i][j]那么对于相邻区间分割点之间有单调关系s[i][j-1] s[i][j] s[i1][j]这是什么意思意思是随着区间右端点向右移动最优分割点不会往回跑随着区间左端点向右移动最优分割点也不会继续向左跑。这给了一个极好的搜索区间计算 dp[i][j] 时不需要从 i 到 j-1 全枚举一遍只需要枚举从 s[i][j-1] 到 s[i1][j] 这一小段即可。从直觉上说如果某个区间变长了一点那么最优的“切点”只会在原来的切点附近略微移动不会发生大的跳动。这个性质一旦成立所有 k 的枚举范围都是常数级别整体复杂度从 O(n^3) 直接掉到 O(n^2)。5.2 Knuth优化代码改造在原来的迭代代码基础上加两个改动单独记录 s[i][j]并且把内层循环范围收紧。for (int len 2; len n; len) { for (int i 1; i len - 1 n; i) { int j i len - 1; dp[i][j] INF; int L s[i][j - 1]; // 下界 int R s[i 1][j]; // 上界 if (L 0) L i; // 处理边界空值 if (R 0) R j - 1; for (int k L; k R; k) { long long 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; } } } }注意 s 数组的初始化。需要在最外层循环之前设置s[i][i] i因为长度为 1 的区间虽然没有实际分割点但在计算长度为 2 的区间时s[i][j-1]会用到s[i][i]s[i1][j]会用到s[i1][i1]。如果不初始化L 和 R 可能是 0导致枚举范围出错。这个优化在 n1000 以上时效果非常明显。原来可能跑 2 到 3 秒甚至更久优化后往往几十毫秒内就能出结果。笔试面试中如果 n 给到 1000 到 5000基本就得靠 Knuth 优化。5.3 什么时候别用Knuth优化Knuth 优化不是所有区间 DP 都能用。它的前提是转移方程满足四边形不等式并且状态转移形式是“两个子区间之和加上合并代价”。矩阵链乘法是经典适用场景这也是它被拿来做例题的原因。遇到一个新题时不要盲目缩小枚举范围。先用朴素 O(n^3) 写一版验证思路再考虑优化。如果题目数据范围不大O(n^3) 本来就能过何必给自己增加复杂度。如果决定要用 Knuth 优化最好先确认一下代价函数的单调性和四边形不等式是否成立或者至少在样例和暴力程序上对拍一下。我自己在实际比赛中吃过亏曾经在一个“区间合并代价不是简单加法”的题目上套了 Knuth 优化结果答案错得很稳定。后来一查那题的合并代价不满足四边形不等式优化范围给错了。所以“会套模板”和“敢套模板”是两码事碰到新题要谨慎。6. 从矩阵链到更多区间DP题目6.1 和石子合并问题的对照石子合并是另一道经典区间 DP问题描述大体是有一排石子堆每堆有一定数量每次只能合并相邻两堆代价是两堆石子数之和问合并成一堆的最小总代价。它的递推公式长这样dp[i][j] min( dp[i][k] dp[k1][j] sum(i, j) )对比矩阵链的公式dp[i][j] min( dp[i][k] dp[k1][j] p[i-1] * p[k] * p[j] )两边的骨架完全一致只有合并代价不同。石子合并的合并代价是区间和跟 k 无关矩阵链的合并代价跟分割点 k 有关。但两者都属于“切一刀拼左右”的区间 DP 模型。理解了矩阵链石子合并基本就是换个代价函数再写一遍。反过来也一样很多看似不同的题剥掉外壳后都是这个模板。6.2 区间 DP 的常见套路从矩阵链乘法里能总结出一套通用的做题流程第一步确认问题是“连续区间”上的最优问题并且子问题也是同类型区间。第二步设计状态 dp[i][j] 表示从 i 到 j 的某个最优值。第三步枚举分割点 k写出转移 dp[i][j] min(dp[i][k] dp[k1][j] cost(i,k,j))。第四步按区间长度从小到大循环保证子区间先算完。第五步如果要求输出方案记录 s[i][j]。这套流程可以解决大量区间 DP 题目。状态不一定是“最小值”也可能是“方案数”“最长序列”甚至“是否可行”。只要转移是在区间内分割核心思想都一样。我个人的建议是在掌握流程后不要急着刷很多题先把矩阵链乘法在纸上亲手推一遍。比如用一个 n4 的例子把所有 dp[i][j] 的值手算出来再和代码结果对照。这个过程能帮你在脑子里建立一张“区间表”后续遇到什么新题都更有画面感。6.3 扩展最优二叉搜索树与多边形剖分矩阵链乘法的转移思路还可以直接迁移到最优二叉搜索树问题。最优二叉搜索树的 dp[i][j] 表示用第 i 个到第 j 个关键字构造最优搜索树的期望搜索代价转移要枚举根节点 k把左右子树拼起来再加上整棵树的深度代价。它同样满足四边形不等式也可以用 Knuth 优化。多边形三角剖分问题也类似把一个凸多边形剖分成三角形要求某种权值和最小分割点就是三角形的一个顶点左右两边分别是子多边形。这类题一看到“在一段区间上取一个点分成两段”的结构就能立刻联想到区间 DP。所以矩阵链乘法不是一道孤立的题它是一系列区间 DP 的入口。把这个模型吃透很多题看起来就不再是背模板而是自然而然地套用同一套思维方式。最后分享一点个人经验。我刚开始写矩阵链乘法时总觉得递推公式简单写代码却容易错尤其在下标上吃了不少亏。后来养成一个习惯拿到题先画区间图把 p 数组和矩阵下标对照好再把转移公式中每一项对应到图上最后才动笔写代码。这个方法看起来笨但确实能省下很多排查错误的时间。如果你也被矩阵链的细节折磨过不妨也试试先把问题拆成“区间怎么切、代价怎么算”代码自然就顺了。