矩阵连乘问题：动态规划解法与区间DP思想详解

1. 从一道让无数人头疼的题说起

矩阵连乘问题，这六个字一出来，学过计算机算法的人脑子里大概会立刻浮现出两个画面：一个是课本上密密麻麻的括号，另一个是考试时盯着题目发呆的自己。我当年第一次接触这个问题的时候，心里想的是——不就是几个矩阵乘在一起吗，从左往右算不就完了？结果一做题才发现，事情远没有这么简单。

这个问题的核心其实非常朴素：给你一串矩阵，比如 A1、A2、A3 一直到 An，它们要连乘起来。矩阵乘法满足结合律，也就是说你可以先算前两个再乘第三个，也可以先算后两个再和第一个乘，最终结果一样。但问题在于，不同的计算顺序，中间产生的计算量可能天差地别。矩阵连乘问题要解决的，就是找到一种加括号的方式，让整个连乘过程所需的标量乘法次数最少。

你可能会问，这有什么实际意义？我举个具体的场景你就明白了。在计算机图形学里，一个三维模型从局部坐标系变换到世界坐标系，再到相机坐标系，最后投影到屏幕上，中间要经过一连串的矩阵乘法。如果这些矩阵的维度搭配不当，计算量可能膨胀几十倍甚至上百倍。在实时渲染的场景下，这就是能不能跑满帧率的区别。再比如神经网络的推理过程，本质上也是大量的矩阵连乘，虽然实际工程中会做各种优化，但底层的思路和矩阵连乘问题是相通的。

所以这个问题不是纯粹的学术练习，它背后有非常实在的工程价值。适合谁来读这篇文章？如果你正在学算法设计与分析，动态规划这一章肯定绕不开矩阵连乘；如果你已经工作了，但每次遇到区间DP的题目还是心里发虚，那这篇文章也能帮你把思路彻底理清楚。我会从最朴素的想法开始，一步步推到动态规划的解法，把每一步的“为什么”都讲透，最后再聊聊实际写代码时容易踩的坑。

2. 暴力解法和它的天花板

2.1 穷举所有加括号方式有多恐怖

要理解动态规划为什么是这个问题的最优解，得先看看不用动态规划会怎样。最直接的想法就是枚举所有可能的加括号方式，然后逐个计算每种方式的乘法次数，取最小值。这个思路本身没错，问题出在数量上。

n 个矩阵连乘，有多少种加括号方式？这个数字叫做卡特兰数，记作 C(n-1)。我列几个数字你感受一下：3 个矩阵有 2 种方式，4 个矩阵有 5 种，5 个矩阵有 14 种，6 个矩阵有 42 种，10 个矩阵有 4862 种。看起来还不算太离谱？那继续：15 个矩阵有 2674440 种，20 个矩阵有 6564120420 种。也就是说，当矩阵数量达到 20 个的时候，暴力枚举的计算量已经超过 65 亿次了。这还只是枚举方案的数量，每种方案还要计算乘法次数，实际运算量更大。

我实测过，在一台普通笔记本上用 Python 写一个纯暴力的递归枚举，n=15 的时候就已经要跑好几分钟了，n=20 直接卡死。这就是暴力解法的天花板——它的时间复杂度是指数级的，稍微大一点的输入就完全不可行。

2.2 为什么暴力解法会重复计算

暴力解法慢的根本原因不是它枚举了太多方案，而是它在枚举过程中做了大量重复计算。我举个简单的例子来说明。

假设有四个矩阵 A1、A2、A3、A4 要连乘。考虑两种加括号方式：((A1A2)(A3A4)) 和 ((A1(A2A3))A4)。第一种方式在计算 A1A2 和 A3A4 的时候，会分别算出这两个子链的最优乘法次数。第二种方式在计算 A2A3 的时候，也会算一次。但更关键的是，如果 n 更大，比如有六个矩阵，那么子链 A2A3A4 的最优解会在多种不同的外层加括号方式中被反复求解。

这就是典型的“重叠子问题”结构。暴力递归的做法是每次遇到一个子问题就重新算一遍，完全不记录之前算过的结果。打个比方，这就像你每次做菜都要重新去菜市场买一遍所有调料，哪怕冰箱里已经有一模一样的。动态规划的核心思想就是把这些子问题的解存起来，下次需要的时候直接查表，不再重复计算。

2.3 从暴力到动态规划的思维跃迁

从暴力解法到动态规划，关键的一步是意识到：整个矩阵链的最优解，可以由它的子链的最优解组合而来。这句话听起来有点抽象，我用一个更具体的说法来解释。

假设最优的加括号方式在某个位置 k 把矩阵链切成了两段：左边是 A1 到 Ak，右边是 Ak+1 到 An。那么左边这段本身一定也是用最优的方式加括号的，右边同理。为什么？因为如果左边有更优的加括号方式，那把它换进去，整个链的总乘法次数只会更少，这就和“当前是最优解”矛盾了。这个性质叫做最优子结构。

有了最优子结构，再加上重叠子问题，动态规划的两个前提条件就都满足了。接下来要做的就是定义状态、写转移方程、确定计算顺序。这三步是动态规划解题的标准流程，矩阵连乘问题可以说是把这套流程体现得最清晰的经典案例之一。

3. 动态规划解法的完整拆解

3.1 状态定义：m[i][j] 到底代表什么

动态规划的第一步永远是定义状态。在矩阵连乘问题里，我们定义 m[i][j] 表示从第 i 个矩阵到第 j 个矩阵这段子链所需的最少标量乘法次数。注意这里的 i 和 j 是矩阵的编号，从 1 开始，i 小于等于 j。

当 i 等于 j 的时候，也就是只有一个矩阵，不需要做任何乘法，所以 m[i][i] = 0。这是状态空间的边界条件，也是整个递推的起点。

除了 m 数组，通常还会额外维护一个 s 数组，s[i][j] 记录的是子链 i 到 j 的最优分割点 k。这个数组不参与最优值的计算，但用来回溯出具体的加括号方案。很多教程只讲 m 数组不讲 s 数组，导致读者虽然知道最少乘法次数是多少，但不知道怎么加括号，这在实际应用中是缺失的一环。

3.2 转移方程：怎么从子问题推出大问题

转移方程是动态规划的灵魂。对于 m[i][j]，我们要考虑所有可能的分割点 k，其中 k 从 i 到 j-1。对于每个 k，计算方式是：先算左边子链 i 到 k 的最少次数 m[i][k]，再算右边子链 k+1 到 j 的最少次数 m[k+1][j]，最后加上这两段结果相乘所需的次数。

最后这部分怎么算？假设矩阵 Ai 的维度是 p[i-1] 乘以 p[i]，那么左边子链的结果矩阵维度是 p[i-1] 乘以 p[k]，右边子链的结果矩阵维度是 p[k] 乘以 p[j]。这两个矩阵相乘需要的标量乘法次数是 p[i-1] 乘以 p[k] 再乘以 p[j]。

所以完整的转移方程是：m[i][j] 等于所有 k 从 i 到 j-1 中，m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j] 的最小值。同时把取得最小值的那个 k 记录到 s[i][j] 里。

这个方程我第一次看的时候觉得挺绕的，后来发现关键是理解 p 数组的含义。p 数组有 n+1 个元素，p[0] 是第一个矩阵的行数，p[1] 是第一个矩阵的列数也是第二个矩阵的行数，以此类推。因为矩阵连乘要求前一个的列数等于后一个的行数，所以 p 数组实际上描述了整条链的维度信息。

3.3 计算顺序：为什么不能按 i 和 j 的自然顺序填表

定义好状态和转移方程之后，下一个问题是：按照什么顺序来计算 m[i][j]？

如果你按照 i 从 1 到 n、j 从 1 到 n 的双重循环来填表，会发现计算 m[i][j] 的时候，需要用到的 m[i][k] 和 m[k+1][j] 可能还没有被计算出来。比如算 m[1][4] 的时候需要 m[1][2] 和 m[3][4]，如果外层循环是 i、内层是 j，那么当 i=1、j=4 的时候，m[3][4] 确实已经算过了（因为 i=3 的循环已经走完了），但 m[1][2] 是在同一轮 i=1 里更早算的，也没问题。但问题是 m[2][4] 这种，当 i=1 的时候还没轮到 i=2，所以 m[2][4] 还没算。

正确的计算顺序是按照子链的长度来。先算所有长度为 1 的子链（就是对角线上的 m[i][i]），再算长度为 2 的，再算长度为 3 的，一直到长度为 n。对于每个固定长度 len，遍历所有可能的起点 i，终点 j 就等于 i+len-1。这样在计算长度为 len 的子问题时，所有长度小于 len 的子问题都已经计算完毕，可以直接查表。

这个顺序我第一次写的时候经常搞错，后来总结了一个简单的记法：外层循环是链长，内层循环是起点。只要记住“先短后长”，就不会出错。

3.4 回溯构造最优加括号方案

算出 m[1][n] 之后，我们知道了最少乘法次数，但还不知道具体怎么加括号。这时候 s 数组就派上用场了。

从 s[1][n] 开始，假设它的值是 k，那么最优方案就是在 k 处把链切成两段：1 到 k 和 k+1 到 n。然后递归地去查 s[1][k] 和 s[k+1][n]，继续切分，直到子链长度为 1 为止。这个过程可以用递归实现，也可以用栈来模拟递归。

我一般喜欢写一个递归函数 print_optimal(i, j)，如果 i 等于 j，就输出 “A” 加上 i 的值；否则先输出一个左括号，递归处理左边，再递归处理右边，最后输出右括号。这样就能把完整的加括号方案打印出来。

4. 手把手带你走一遍完整实例

4.1 设定矩阵维度并列出 p 数组

光看公式容易晕，我们拿一个具体的例子从头到尾算一遍。假设有四个矩阵 A1、A2、A3、A4，它们的维度分别是：

• A1：10 行 20 列
• A2：20 行 30 列
• A3：30 行 40 列
• A4：40 行 30 列

注意 A1 的列数 20 等于 A2 的行数 20，A2 的列数 30 等于 A3 的行数 30，A3 的列数 40 等于 A4 的行数 40，所以这条链是可以连乘的。

对应的 p 数组是：[10, 20, 30, 40, 30]。一共 5 个元素，p[0]=10，p[1]=20，p[2]=30，p[3]=40，p[4]=30。

4.2 逐步填表计算 m 和 s

先初始化对角线：m[1][1]=m[2][2]=m[3][3]=m[4][4]=0。

链长为 2 的情况：

m[1][2]：只有 k=1 一种分割。m[1][1]+m[2][2]+p[0]p[1]p[2] = 0+0+102030 = 6000。s[1][2]=1。

m[2][3]：k=2。m[2][2]+m[3][3]+p[1]p[2]p[3] = 0+0+203040 = 24000。s[2][3]=2。

m[3][4]：k=3。m[3][3]+m[4][4]+p[2]p[3]p[4] = 0+0+304030 = 36000。s[3][4]=3。

链长为 3 的情况：

m[1][3]：k 可以取 1 或 2。

k=1：m[1][1]+m[2][3]+p[0]p[1]p[3] = 0+24000+102040 = 24000+8000 = 32000。

k=2：m[1][2]+m[3][3]+p[0]p[2]p[3] = 6000+0+103040 = 6000+12000 = 18000。

取最小值 18000，对应 k=2。所以 m[1][3]=18000，s[1][3]=2。

m[2][4]：k 取 2 或 3。

k=2：m[2][2]+m[3][4]+p[1]p[2]p[4] = 0+36000+203030 = 36000+18000 = 54000。

k=3：m[2][3]+m[4][4]+p[1]p[3]p[4] = 24000+0+204030 = 24000+24000 = 48000。

取最小值 48000，对应 k=3。所以 m[2][4]=48000，s[2][4]=3。

链长为 4 的情况：

m[1][4]：k 取 1、2、3。

k=1：m[1][1]+m[2][4]+p[0]p[1]p[4] = 0+48000+102030 = 48000+6000 = 54000。

k=2：m[1][2]+m[3][4]+p[0]p[2]p[4] = 6000+36000+103030 = 42000+9000 = 51000。

k=3：m[1][3]+m[4][4]+p[0]p[3]p[4] = 18000+0+104030 = 18000+12000 = 30000。

取最小值 30000，对应 k=3。所以 m[1][4]=30000，s[1][4]=3。

4.3 回溯得到最优加括号方式

从 s[1][4]=3 开始，说明最优方案在位置 3 处分割，即 (A1A2A3)(A4)。

然后看左边子链 1 到 3，s[1][3]=2，说明在位置 2 处分割，即 (A1A2)(A3)。

再看左边子链 1 到 2，s[1][2]=1，说明在位置 1 处分割，即 (A1)(A2)。

所以最终的加括号方式是：((A1A2)A3)A4。

验证一下计算量：A1A2 得到 10x30 的矩阵，乘法次数 102030=6000；再乘 A3 得到 10x40 的矩阵，乘法次数 103040=12000；再乘 A4 得到 10x30 的矩阵，乘法次数 104030=12000。总次数 6000+12000+12000=30000，和 m[1][4] 一致。

如果换成从左往右依次乘：A1A2 是 6000 次，得到 10x30；再乘 A3 是 103040=12000 次，得到 10x40；再乘 A4 是 104030=12000 次。总次数也是 30000。这个例子里两种方式恰好一样，但换一组维度数据结果就会不同。你可以自己试试把 A4 改成 40 行 50 列，再算一遍，就能看到差异了。

5. 代码实现与关键细节

5.1 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 def print_optimal_parens(s, i, j): if i == j: return f"A{i}" else: k = s[i][j] left = print_optimal_parens(s, i, k) right = print_optimal_parens(s, k+1, j) return f"({left}{right})"

这段代码里，m 和 s 都用了 n+1 的大小，因为矩阵编号从 1 开始，索引 0 的位置空着不用。外层循环 length 从 2 到 n，内层 i 从 1 到 n-length+1，j 由 i 和 length 算出。k 的循环范围是 i 到 j-1。

5.2 数组索引的常见坑

写这段代码最容易出错的地方就是索引。p 数组的长度是 n+1，p[0] 到 p[n]。m 和 s 是 (n+1) x (n+1) 的二维数组，但实际只用到 1 到 n 的行和列。

我在早期写的时候经常把 p[i-1]*p[k]*p[j] 写成 p[i]*p[k]*p[j]，结果算出来的值偏大或者偏小，排查半天才发现是索引差了一位。记住一个口诀：左边子链的起始矩阵是 Ai，它的行数是 p[i-1]；分割点矩阵是 Ak，它的列数是 p[k]；右边子链的结束矩阵是 Aj，它的列数是 p[j]。所以乘起来就是 p[i-1] * p[k] * p[j]。

还有一个坑是内层循环 i 的上界。当 length 固定的时候，j = i + length - 1 必须小于等于 n，所以 i 最大是 n - length + 1。如果写成 n - length，就会漏掉最后一个子链。

5.3 时间复杂度与空间复杂度分析

矩阵连乘的动态规划解法，时间复杂度是 O(n^3)。为什么？三重循环：外层 length 有 n-1 种取值，中层 i 平均有 n/2 种取值，内层 k 平均有 n/2 种取值，乘起来大约是 n 的立方级别。空间复杂度是 O(n^2)，因为要维护两个 n+1 乘 n+1 的二维数组。

和暴力解法的指数级复杂度比起来，O(n^3) 已经是巨大的进步了。n=100 的时候，n^3 是一百万次运算，现代计算机毫秒级就能完成。n=1000 的时候是十亿次，大概几秒钟。当然实际工程中如果矩阵链特别长，还会用一些优化技巧，比如 Knuth 优化可以把复杂度降到 O(n^2)，但那个属于进阶内容，先把基础的 O(n^3) 吃透更重要。

6. 实际写代码时踩过的坑和排查技巧

6.1 常见错误速查表

6.2 调试时最有用的三个技巧

第一个技巧是打印中间表。在填表的过程中，把 m 和 s 的当前状态打印出来，和手算的结果逐格对比。我一般会在每算完一个 length 之后打印一次，这样能快速定位到是哪一层出了问题。

第二个技巧是用小规模数据验证。先用 n=3 或 n=4 的小例子跑一遍，手算结果和程序结果对上了，再换更大的数据。很多人一上来就用 n=10 的数据测试，结果错了也不知道错在哪一步。

第三个技巧是单独测试回溯函数。把 m 和 s 用一组已知正确的数据填好，然后只调用 print_optimal_parens，看输出的括号方案是否合理。这样可以把填表逻辑和回溯逻辑分开调试，缩小问题范围。

6.3 一个容易被忽略的边界情况

当 n=1 的时候，也就是只有一个矩阵，不需要做任何乘法，最少次数是 0。很多代码在处理 n=1 的时候会出问题，因为外层循环 length 从 2 开始，根本不会进入，m[1][1] 保持初始值 0，这没问题。但回溯函数 print_optimal_parens 在 i==j 的时候要能正确返回 “A1”，不能报错。

还有一个边界是 n=0，也就是没有矩阵。虽然实际中很少遇到，但写通用函数的时候最好加一个判断，n=0 直接返回 0 或者空字符串。

7. 这个算法思想还能用在哪里

矩阵连乘问题虽然本身是一个具体的算法题，但它背后的动态规划思想可以迁移到很多其他问题上。最直接的一类就是区间DP，比如石子合并问题、多边形三角剖分问题、最优二叉搜索树问题，它们的共同特点是：一个大区间的最优解由它的子区间的最优解组合而来，而且子区间之间有重叠。

我在实际工作中遇到过一个日志分析的需求，要把多条日志记录合并成一条摘要，合并的顺序会影响中间结果的大小，进而影响处理时间。当时就是用区间DP的思路来做的，把每条日志看作一个“矩阵”，合并操作看作“乘法”，中间结果的大小看作“乘法次数”，套用矩阵连乘的框架，很快就找到了最优的合并顺序。

另一个常见的应用场景是编译器优化中的表达式求值顺序。编译器在把表达式翻译成中间代码的时候，需要决定先算哪一部分后算哪一部分，以减少临时变量的数量和寄存器压力。虽然实际的编译器会考虑更多因素，但核心的优化思路和矩阵连乘问题是相通的。

学算法最怕的就是只记住代码模板，不理解背后的思想。矩阵连乘问题是一个非常好的跳板，把它的状态定义、转移方程、计算顺序、回溯构造这四个环节都吃透了，再去看其他区间DP问题，你会发现套路都是类似的。区别只在于状态的含义和转移方程的具体形式，骨架是一样的。

我个人在实际刷题和做项目的过程中体会到，动态规划最难的不是写代码，而是想清楚状态怎么定义、转移怎么推导。这两步想明白了，代码就是水到渠成的事情。矩阵连乘问题之所以经典，就是因为它把这两个难点都体现得很清晰，同时又没有太多额外的干扰因素。把它彻底搞懂，对动态规划的理解会上一个台阶。