矩阵连乘问题Matrix Chain MultiplicationMCM是《计算理论与算法分析设计》课程动态规划章节里最经典的案例也可能是我见过“听课懂了、动手就错”发生率最高的算法题。它要解决的问题非常简单给定一串满足相乘条件的矩阵找出一种加括号的方式让整个连乘过程的标量乘法次数最少。难点在于不同括号方案的计算量差距极大而可行的方案总数又爆炸式增长必须用动态规划才能高效求解。这篇文章我会从问题建模、卡特兰数的暴力不可行性讲起推导出最优子结构和递推公式再给出完整可运行的代码、括号方案的重建方法、复杂度分析最后重点整理我自己教学和代码评审中遇到的六大翻车现场。适合正在上算法课的同学、准备考研复试和面试的开发者也适合想彻底搞懂区间 DP 的每一位读者。1. 问题到底是什么这不是算乘法而是选括号1.1 一个例子看出差距先看最简单的情况三个矩阵 A1、A2、A3 连乘。学过线性代数的都知道矩阵乘法满足结合律也就是说 (A1A2)A3 和 A1(A2A3) 算出来的结果完全一样。但两种方式的计算量可能差出一个数量级。假设维度分别是A110×100A2100×5A35×50两个数字相乘算一次标量乘法。先算方案一 (A1A2)A3A1×A2 需要 10×100×5 5000 次得到中间结果 10×5再乘 A3 需要 10×5×50 2500 次总共 7500 次。再算方案二 A1(A2A3)A2×A3 需要 100×5×50 25000 次得到中间结果 100×50再乘 A1 需要 10×100×50 50000 次总共 75000 次。同样的三个矩阵仅仅换了一个加括号的方式计算量差了整整 10 倍。换成维度差别更悬殊、链条更长的矩阵链这个差距会以指数级别扩大。所以矩阵连乘问题的本质不是“会不会乘矩阵”而是“怎么选择括号方案让标量乘法总次数最小”。这个问题也确有真实工程出处图形学里的变换矩阵、深度学习中的批量矩阵运算、科学计算里的大规模方程组求解都会遇到很长的矩阵链。提前算好最优括号方案能为一次计算省下大把算力尤其当矩阵维度大、链条长的时候收益非常明显。1.2 数学前提与问题建模为了一般化描述约定矩阵 Ai 的维度是 p[i-1]×p[i]。这里引入一个长度为 n1 的维度数组 p而不是给每个矩阵各存两组维度。这样做的原因是相邻矩阵能相乘天然要求 Ai 的列数等于 Ai1 的行数因此整条链只要有 p[0]、p[1]、……、p[n] 这 n1 个值就能完整描述全部信息p[i-1] 和 p[i] 分别是 Ai 的行数和列数。于是问题正式变成给定维度链 p[0..n]求一种括号化方案使得计算 A1×A2×...×An 所需的标量乘法总次数最少。注意矩阵乘法必须满足结合律任意合法括号方案算出的最终结果都一样这正是“选括号”有意义的大前提。如果换成不满足结合律的运算这个问题根本不存在。2. 暴力枚举为什么撑不下去2.1 方案数量是卡特兰数很多同学的第一反应是把所有括号方案枚举一遍找出代价最小的不就行了先别急着写代码算一算方案数量再说。n 个矩阵的合法括号方案数是卡特兰数 C(n-1)。这个序列可以用递推式 T(n) sum(T(k)×T(n-k)) 生成它描述的是“最后一次切分后两段各自再切分”的递归计数。这个数列的增长速度非常惊人n32 种n514 种n104862 种n15约 267 万种n20约 17.7 亿种也就是说即使只处理 20 个矩阵暴力枚举就要尝试超过 17 亿种方案。就算每种方案只做一次简单的代价估算现代 CPU 也要跑很久n 一旦到 30 以上就彻底没有可行空间了。而实际工程中几百上千的矩阵链很常见暴力枚举连边都沾不上。这个数量级的直觉非常重要很多面试题故意把 n 设到 50 甚至 100目的就是逼你放弃枚举思路。2.2 递归树里的重复计算如果把解空间按“最后一次乘法发生在哪里”划分会得到一个天然递归的结构A1...An 的最后一次乘法必然是把整条链切成 A1...Ak 和 Ak1...An 两段分别算完后再相乘。于是枚举方案本质上就是递归地枚举所有可能的 k。问题在于这棵递归树里充斥着大量重复子问题。比如计算区间 [1..5] 需要展开 [2..5]计算 [1..4] 也要展开 [2..4]向下递归时[3..5] 这种小区间会被无数个大区间的展开过程反复碰到。子问题反复出现、完全重复计算这正是动态规划最擅长抓住的特征。所以不要急着写递归先静下来想想能不能把每个区间的最优值只算一次存起来复用能这就是备忘录再进一步能不能直接按区间长度从小到大迭代填表也能。后一种思路就是标准解法。3. 动态规划设计从递推公式到填表顺序3.1 最优子结构与递推公式推导设 m[i][j] 表示计算 Ai...Aj 所需的最少标量乘法次数。当 i 等于 j 时单个矩阵不需要任何乘法所以边界条件是 m[i][i]0。这个“单个元素代价为零”的设定几乎所有区间 DP 都一样它是一切递推的起点。关键在于 i 小于 j 的情形。最后一次乘法一定发生在某个切分点 k 处把区间 [i,j] 分成 [i,k] 和 [k1,j] 两段其中 k 取 i 到 j-1 之间的任意值。如果整个区间的最优方案是在 k 处切开的那么两个子区间 [i,k] 和 [k1,j] 的内部方案也一定各自最优。这个性质可以用经典的“剪贴论证”证明假如 [i,k] 存在比 m[i][k] 更省的内部方案直接把它替换进整体方案总代价会更低这就与“整体最优”矛盾了。因此大问题的最优解一定包含子问题的最优解这就是最优子结构。有了最优子结构递推公式水到渠成m[i][j] min( m[i][k] m[k1][j] p[i-1]×p[k]×p[j] )其中 i ≤ k j最后一项 p[i-1]×p[k]×p[j] 是把两个中间结果相乘的代价。为什么是这个值因为 Ai...Ak 的结果矩阵维度是 p[i-1]×p[k]Ak1...Aj 的结果矩阵维度是 p[k]×p[j]两者相乘需要 p[i-1]×p[k]×p[j] 次标量乘法。这个“结果维度来自区间两端的原始维度”的规律是区间 DP 里反复出现的关键务必记牢。3.2 手算一个完整例子四个矩阵为了把这个公式落到地上我建议你跟我一起手算一遍保证这一遍之后你对填表顺序的理解会完全不一样。假设维度数组 p [3, 5, 2, 8, 1]也就是 A1 是 3×5A2 是 5×2A3 是 2×8A4 是 8×1。先算所有长度为 2 的区间也就是两个矩阵直接相乘的代价m[1][2] 3×5×2 30m[2][3] 5×2×8 80m[3][4] 2×8×1 16再算长度为 3 的区间。m[1][3] 有两种切法k1 时代价是 0803×5×8200k2 时代价是 3003×2×878取较小值所以 m[1][3]78切分点记 k2。m[2][4] 同理k2 代价 0165×2×126k3 代价 8005×8×1120所以 m[2][4]26切分点 k2。最后算长度为 4 的区间 m[1][4]这是整个问题的答案k10263×5×141k230163×2×152k37803×8×1102最小值是 41切分点 k1。所以最优括号方案是 (A1(A2(A3A4)))。可以验证一下A3A4 花 16 次得到 2×1 结果A2 乘它花 5×2×110 次得到 5×1 结果A1 乘它花 3×5×115 次。16101541完全对得上。这个例子建议你亲手算一遍算完再看代码理解会深很多。3.3 填表顺序先长度再起点最后切点递推公式里有个容易被忽略的细节m[i][j] 依赖的两个子问题 m[i][k] 和 m[k1][j]区间长度都比 [i,j] 短。换句话说要算长区间必须先算完所有更短的区间。所以填表必须按照“区间长度从小到大”的顺序来。很多初学者一上来就按 i 从 1 到 n、j 从 i1 到 n 的“行优先”顺序填结果发现 m[k1][j] 还没被算到拿到的全是初始值答案自然错得离谱。正确的三层循环结构是外层枚举区间长度 len从 2 到 n中层枚举起点 i得到终点 jilen-1内层枚举切分点 k。这个“先定长度、再定起点、最后枚举切点”的框架是区间 DP 的通用骨架石子合并、最优二叉搜索树、多边形剖分全都长一个样学会一次受益终身。4. 核心代码实现与括号方案重建4.1 C 核心实现直接给一段我常用的实现注释写在代码后的要点里。#include vector #include climits using namespace std; const long long INF 1e18; long long matrixChainOrder(const vectorlong long p, vectorvectorlong long m, vectorvectorint s) { int n p.size() - 1; m.assign(n 1, vectorlong long(n 1, 0)); s.assign(n 1, vectorint(n 1, 0)); for (int len 2; len n; len) { for (int i 1; i n - len 1; i) { int j i len - 1; m[i][j] INF; for (int k i; k j; k) { long long 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[1][n]; }先说数组尺寸。m 和 s 都开成 (n1)×(n1)但实际只用下标 1 到 n第 0 行第 0 列是纯填充位。这么做是为了让所有公式和下标都是从 1 开始的和教科书上的伪代码一一对应排查问题时不容易被 0 基下标绕晕代价只是多一点几乎可以忽略的内存。再说类型。维度数组 p 和代价数组 m 一定要用 long long很多人在这里吃亏。以为最大代价也就几百万实际上 n50、维度几百上千时单次合并代价 p[i-1]×p[k]×p[j] 就能到亿级累加后 int 必炸。用 long long 一步到位省得后面花一晚上查“为什么答案突然变成负数”。最后说切分点表 s。s[i][j] 存的是区间 [i,j] 的最优切分点 k。如果题目只要求输出最小代价s 完全可以不建但只要涉及还原括号方案s 就必不可少。我见过不少同学为了省空间省掉 s 表最后输出括号方案时傻眼只能推倒重来。4.2 输出最优括号方案只算最小代价还不够作业和面试里经常要求输出具体的括号方案。这个环节用上 s 表代码非常简洁void printParens(const vectorvectorint s, int i, int j) { if (i j) { cout A i; return; } cout (; printParens(s, i, s[i][j]); printParens(s, s[i][j] 1, j); cout ); }调用 printParens(s, 1, n) 就能输出类似 (A1(A2(A3A4))) 的结果。这里有个非常关键的细节递归时必须直接用 s[i][j] 作为当前区间的切分点而不是重新去“当前看起来最优”的位置切。因为 s 表是动态规划阶段经过全局比较后留下的最终答案任何重新贪心或重新计算都可能选出局部最优而非全局最优输出结果自然就错了。这是新手最容易犯的逻辑错误务必警惕。4.3 Python 实现参考如果你用 Python 写逻辑完全一样只是语法上要自己初始化二维表。def matrix_chain_order(p): n len(p) - 1 m [[0] * (n 1) for _ in range(n 1)] s [[0] * (n 1) for _ in range(n 1)] for length in range(2, n 1): for i in range(1, n - length 2): j i length - 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有同学问 Python 能不能把 m 压成一维数组滚动更新。我的答案是区间 DP 的滚动优化不像背包问题那样直接因为 m[i][j] 依赖的是不同起点、不同终点的交叉状态强行压成一维会丢失必要的信息。m 表的 O(n²) 空间在绝大多数场景下完全够用不必为了省内存把代码复杂度抬高一个档次。5. 复杂度分析与进阶优化方向5.1 时间复杂度为什么是 O(n³)外层 len 从 2 到 n 共约 n 层中层 i 的取值最多 n 个内层 k 最多 len-1 次三个循环嵌套起来规模是 n³ 量级所以复杂度记作 O(n³)。如果算得更精确一点内层循环总的执行次数是 sum(len2..n) (n-len1)×(len-1)展开后大约等于 n³/6。换句话说实际常数因子只有约六分之一这个常数在 O(n³) 算法里已经相当友好了。n100 时内层大约执行 16 万次n1000 时大约 1.6 亿次——C 秒出结果Python 会明显吃力。这也解释了为什么这类题目给的数据范围普遍在 n≤500 左右再大就要另想优化办法了。空间复杂度则是 O(n²)因为 m 和 s 各占一个 (n1)×(n1) 的二维表。5.2 能不能更快Knuth 优化与记忆化搜索矩阵连乘的递推满足四边形不等式最优切分点具有单调性因此可以运用 Knuth 优化内层 k 的搜索范围从整个 [i,j] 缩小到 s[i][j-1] 到 s[i1][j] 之间平均复杂度能从 O(n³) 降到接近 O(n²)。这个优化的直觉可以打个比方你在一排货架上找某件商品的最优位置如果已经知道左边一格和右边一格各自的最优位置在递推函数足够“规矩”的前提下你要找的位置大概率不会跑出这两者之间。四边形不等式保证的正是这种“夹逼搜索”的安全性。不过我的建议是初学阶段先把 O(n³) 的标准实现吃透Knuth 优化当作延伸阅读。大部分场景 n 根本到不了需要优化的规模而 Knuth 优化的边界条件一旦写错排查难度比标准写法高一个档次。另外自顶向下的记忆化搜索在这个问题上也是一个完全合法的方案复杂度同样是 O(n³)记忆化可以避免重复递归展开。但它有递归栈消耗、常数更大在处理 n 比较大或递归深度受限的情况时不如迭代写法稳。工程实现优先迭代理解概念时可以两个都写一遍互相验证。6. 实战经验常见错误与排查技巧6.1 六个最容易翻车的现场这些年批改作业、做代码评审矩阵连乘实现在下面这几个点上翻车率最高。整理成表格方便大家对号入座。症状根因正确做法结果比正确答案小很多m[i][j] 初始化为 0min 比较永远不更新每个 m[i][j] 先置为 INF 或极大值结果比正确答案大维度数组下标写错把 p[i-1] 写成 p[i]反复核对 p 的下标语义再动手数组越界或段错误没有留出 n1 的尺寸m、s 统一开 (n1)×(n1)小数据对、大数据错用 int 存代价溢出成负数全部换成 long long算得非常慢甚至超时填表顺序错了按行优先填外层必须按区间长度 len 枚举输出括号顺序完全不对重建时没用 s 表而是重新贪心递归切分只认 s[i][j]6.2 一个反复出现的错误示范最大的坑是填表顺序。有人觉得反正所有 m[i][j] 最终都会被算出来循环顺序无所谓于是写了“i 从 1 到 nj 从 i1 到 nk 从 i 到 j-1”的代码。n 很小时可能碰巧蒙对但 n 稍大m[2][5] 这种需要依赖 m[3][5] 的状态时m[3][5] 还没被算到取到的就是 INF 或 0结果当然全错。我在代码评审里见过不下十次这类问题。记住口诀区间 DP先定长度再定起点最后枚举切点。6.3 怎么验证你的实现是对的写出代码后强烈建议先做一个小规模的暴力对照验证。写一个递归枚举所有括号方案的函数n 不超过 8 时完全可行随机生成多组维度数据对比暴力结果和 DP 结果是否一致。这一步能筛掉绝大多数逻辑错误。再准备一个手动可验算的固定用例比如上面算过的 p[3,5,2,8,1]正确答案是 41括号方案是 (A1(A2(A3A4)))。把这个用例写成单元测试比任何自查都管用。还有一个常识性校验无论怎么加括号最终结果矩阵的行数一定是 p[0]、列数一定是 p[n]。如果代码算出的代价是 0或者括号方案里出现了维度对不上的乘法优先检查是不是把单个矩阵的乘法也算进去了或者下标挪了一位。6.4 考试和面试里到底考什么从考试角度矩阵连乘几乎必考两类题一类是给定维度数组手工填 m 表和 s 表写出最优括号方案另一类是写出递推公式并分析复杂度。前者考填表顺序的理解后者考最优子结构的掌握。很多同学公式推导没问题一填表就错问题几乎都出在没按区间长度从小到大填。从面试角度这道题是动态规划的经典敲门砖。面试官想看的是你能不能三句话讲清楚状态定义、递推公式和填表顺序能不能意识到卡特兰数意味着暴力不可行能不能用 s 表还原方案。把这三个点讲透比背一百遍模板都有说服力。如果面试官追问优化能说出 Knuth 优化的大致思路就是明显的加分项。最后说一点个人体会。我每次带新人做矩阵连乘都会让他们先手工填一次四个矩阵的 m 表和 s 表再回头读代码。填表的过程看起来慢但它能把“先短区间后长区间”这个顺序变成肌肉记忆。很多同学做区间 DP 卡壳根因不是不会递推公式而是没有真正想明白填表顺序为什么必须这样设计。学完这道题之后建议顺手把石子合并、最优二叉搜索树、多边形剖分这些同类问题都过一遍——它们的递推框架几乎一模一样区别只在合并代价那一项的形式。能把这几个题串起来理解动态规划这一章你就真正过关了。
