矩阵连乘问题：动态规划从原理到工程实践-北京尧图网络

1. 从一次面试翻车说起矩阵连乘到底在算什么几年前我帮一个朋友做模拟面试随手出了一道矩阵连乘的题目。他本科学的是软件工程成绩不差结果在白板上写了二十分钟最后憋出来一个暴力递归时间复杂度直接爆炸。他跟我说了一句话让我印象很深“我知道要用动态规划但我不知道那个状态转移方程到底是怎么推出来的。”这个场景其实非常典型。矩阵连乘问题几乎是所有算法教材里讲动态规划的入门案例但很多人学完之后只记住了一个公式换一道题就不会了。问题出在哪出在大家把它当成一道“背公式”的题而不是一个“做决策”的题。先把问题本身说清楚。给定一串矩阵 A1、A2、A3 一直到 An要计算它们的连乘积 A1×A2×...×An。矩阵乘法满足结合律也就是说你可以先算前两个再乘第三个也可以先算后两个再和第一个相乘最终结果一样。但不同的计算顺序中间产生的标量乘法次数差别巨大。举个具体的例子。假设有三个矩阵A1 是 10×100A2 是 100×5A3 是 5×50。如果按 ((A1×A2)×A3) 的顺序算第一步 A1×A2 需要 10×100×5 5000 次标量乘法得到一个 10×5 的矩阵第二步再乘 A3需要 10×5×50 2500 次。总共 7500 次。但如果按 (A1×(A2×A3)) 的顺序算第一步 A2×A3 需要 100×5×50 25000 次第二步 A1 乘这个结果需要 10×100×50 50000 次总共 75000 次。同样的三个矩阵计算顺序不同运算量差了十倍。这就是矩阵连乘问题的核心给定矩阵链的维度序列找到一种加括号的方式使得总的标量乘法次数最少。注意我们不是真的要去算矩阵的值而是只做“决策”——决定怎么加括号。这个区分很重要因为一旦你理解了这一点就会明白为什么动态规划是天然适合这个问题的工具。这篇文章我会从零开始把矩阵连乘问题的动态规划解法彻底讲透。不只是给你一个状态转移方程而是让你理解这个方程是怎么一步步推出来的为什么这样定义状态填表的顺序为什么不能反以及在实际编码中容易踩的坑。适合正在学算法的大学生、准备面试的开发者以及任何想真正搞懂动态规划的人。2. 为什么贪心不好使最优子结构到底藏在哪2.1 贪心策略的诱惑与失败第一次接触这个问题的人很容易想到一个贪心策略每次选择乘法代价最小的那两个矩阵先乘。听起来很合理对吧但稍微想一下就会发现漏洞。假设矩阵链的维度是 [30, 35, 15, 5, 10, 20, 25]对应六个矩阵。如果贪心地找当前代价最小的一对可能会先合并中间某两个但这个局部最优的选择可能导致后续的合并代价飙升。贪心算法在这里失效的根本原因是当前看起来最便宜的一步可能会改变后续所有矩阵的维度结构从而影响全局代价。这和活动选择问题、霍夫曼编码那些能用贪心解决的问题不一样。贪心能成立的前提是“局部最优能推导出全局最优”而矩阵连乘问题不满足这个性质。你没法只看眼前一步就做出正确决策必须通盘考虑。2.2 最优子结构的发现过程那动态规划为什么能行关键在于发现问题的最优子结构。我们换个角度想。对于矩阵链 A1×A2×...×An最终一定要在某一个位置 k 把它分成两部分左边是 A1×...×Ak右边是 A(k1)×...×An然后这两部分的结果再相乘。这个 k 可以是 1 到 n-1 之间的任何一个位置。假设最优的加括号方案就是在位置 k 处分割的。那么左边这部分 A1×...×Ak 的加括号方式一定也是所有可能方式中最优的右边同理。为什么因为如果左边存在一种更少乘法次数的加括号方式我们把它替换进去总的代价只会更小那原来的方案就不是最优的了。这就是最优子结构的本质一个问题的最优解包含了其子问题的最优解。这个性质一旦确认就可以写出递归关系了。设 m[i][j] 表示计算矩阵链 Ai×A(i1)×...×Aj 所需的最少标量乘法次数。那么当 i j 时只有一个矩阵不需要做任何乘法m[i][j] 0。当 i j 时我们枚举所有可能的分割点 ki ≤ k jm[i][j] min{ m[i][k] m[k1][j] p(i-1)×p(k)×p(j) }。这里的 p 数组是维度序列。如果矩阵 Ai 的维度是 p(i-1) × p(i)那么 Ai×...×Aj 的结果矩阵维度就是 p(i-1) × p(j)。最后那一项 p(i-1)×p(k)×p(j) 就是左右两部分结果相乘的代价。2.3 重叠子问题的验证光有最优子结构还不够还得有重叠子问题动态规划才比朴素递归有优势。矩阵连乘问题里重叠子问题非常明显。比如计算 m[1][5] 的时候你需要 m[1][1]m[2][5]、m[1][2]m[3][5]、m[1][3]m[4][5]、m[1][4]m[5][5]。而计算 m[1][4] 的时候你又需要 m[1][1]m[2][4]、m[1][2]m[3][4]、m[1][3]m[4][4]。你会发现 m[1][2]、m[1][3] 这些子问题被反复用到。如果纯递归不记忆化时间复杂度是指数级的因为同一个子问题会被重复计算无数次。而用动态规划自底向上填表每个子问题只算一次时间复杂度降到 O(n³)。这就是为什么我们要用 DP 而不是暴力递归。提示判断一个问题能不能用 DP就看两点——有没有最优子结构有没有重叠子问题。两个都满足DP 基本就是正确方向。3. 手把手推导状态转移从递归式到填表顺序3.1 状态定义的直觉解释m[i][j] 这个状态定义看起来简单但初学者容易犯一个错误把它理解成“矩阵 Ai 到 Aj 相乘的结果矩阵”。不是的。m[i][j] 是一个数字表示的是最少乘法次数不是矩阵本身。这个区分很关键因为我们的目标是最小化运算量而不是真的去算矩阵乘积。另一个容易混淆的地方是 p 数组的索引。如果矩阵链是 A1, A2, ..., An那么 p 数组有 n1 个元素p[0] 到 p[n]。矩阵 Ai 的维度是 p[i-1] × p[i]。这个索引关系一定要搞清楚否则写代码的时候数组越界或者算错代价都是常见的事。3.2 递归式的逐项拆解把递归式 m[i][j] min{ m[i][k] m[k1][j] p[i-1]×p[k]×p[j] } 拆开来看m[i][k]左边子链 Ai×...×Ak 的最少乘法次数。m[k1][j]右边子链 A(k1)×...×Aj 的最少乘法次数。p[i-1]×p[k]×p[j]左右两部分的结果矩阵相乘的代价。左边结果矩阵是 p[i-1]×p[k]右边结果矩阵是 p[k]×p[j]两者相乘需要 p[i-1]×p[k]×p[j] 次标量乘法。三项加起来就是选择分割点 k 时的总代价。枚举所有可能的 k取最小值就是 m[i][j]。这个式子看起来不复杂但有一个细节很多人第一次学的时候会忽略p[k] 既是左边结果矩阵的列数也是右边结果矩阵的行数。这不是巧合而是因为矩阵链的连续性——Ak 的列数等于 A(k1) 的行数所以它们才能相乘。这个性质保证了整个链是可以合法相乘的。3.3 填表顺序为什么必须按链长递增这是矩阵连乘 DP 最容易出错的地方。很多人写代码的时候直接写两层循环 for i in 1..n, for j in i..n然后发现结果不对。为什么因为 m[i][j] 依赖于比它更短的子链的值。如果你按 i 和 j 的自然顺序填表可能在计算 m[1][5] 的时候m[3][4] 还没算出来。正确的填表顺序是按链长也就是 j - i 1从小到大。先算所有长度为 2 的子链即相邻两个矩阵再算长度为 3 的一直到长度为 n。这样在计算长链的时候它需要的所有短链子问题都已经计算完毕了。用代码表达就是for length in range(2, n 1): # 链长从2到n 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[k1][j] p[i-1]*p[k]*p[j] if cost m[i][j]: m[i][j] cost s[i][j] k # 记录最优分割点这段代码里s[i][j] 用来记录最优分割点方便后续还原加括号方案。这个辅助数组在实际应用中很重要因为很多时候你不只想知道最少次数还想知道具体怎么加括号。注意三层循环的顺序不能乱。最外层必须是链长中间是起点最内层是分割点。如果你把链长和起点调换或者把分割点放到外面结果都会出错。4. 代码落地从伪代码到可运行的完整实现4.1 完整代码与逐行注释下面是一份可以直接运行的 Python 实现包含了计算最少乘法次数和还原最优加括号方案两部分def matrix_chain_order(p): p: 维度数组长度为 n1矩阵 Ai 的维度为 p[i-1] x p[i] 返回: (m, s)m[i][j] 为最少乘法次数s[i][j] 为最优分割点 n len(p) - 1 # 矩阵个数 # m[i][j] 表示计算 Ai..Aj 的最少乘法次数 m [[0] * (n 1) for _ in range(n 1)] # s[i][j] 记录 Ai..Aj 的最优分割点 s [[0] * (n 1) for _ in range(n 1)] # length 是子链的长度从2个矩阵开始 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[k1][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): 根据 s 数组还原最优加括号方案 if i j: return fA{i} k s[i][j] left print_optimal_parens(s, i, k) right print_optimal_parens(s, k 1, j) return f({left} x {right}) # 测试 p [30, 35, 15, 5, 10, 20, 25] m, s matrix_chain_order(p) print(f最少乘法次数: {m[1][6]}) print(f最优加括号方案: {print_optimal_parens(s, 1, 6)})运行结果会输出最少乘法次数和对应的加括号方案。你可以手动验证一下把不同的加括号方式代进去算确认 DP 给出的确实是最少的。4.2 空间优化真的需要二维数组吗标准的 DP 解法用两个 n×n 的二维数组空间复杂度 O(n²)。对于大多数场景这已经足够了但如果矩阵链特别长比如 n 上万O(n²) 的空间可能就不太够了。有一种空间优化思路是利用平行四边形不等式也叫 Knuth 优化可以把时间复杂度从 O(n³) 降到 O(n²)空间也能相应优化。但这个优化有前提条件不是所有维度序列都满足。在实际工程中除非你确实遇到了性能瓶颈否则没必要上这个优化标准解法已经够用。另一个常见的空间优化是滚动数组但因为 m[i][j] 依赖于所有更短的子链不是只依赖前一行所以简单的滚动数组在这里不适用。这一点和背包问题不一样不要想当然地套用。4.3 还原方案时的递归陷阱print_optimal_parens 这个函数看起来简单但有一个坑如果矩阵链很长递归深度可能达到 n在 Python 里默认递归深度是 1000n 超过这个值就会报 RecursionError。解决办法要么用迭代方式重写要么手动设置递归深度上限。迭代版本的思路是用栈模拟递归或者直接根据 s 数组自底向上构造括号字符串。后者实现起来稍微复杂一些但更稳健。在实际项目中如果 n 可能很大建议直接用迭代版本。5. 实测中的意外与排查那些教材不会告诉你的坑5.1 维度数组的索引错位这是最常见的错误没有之一。很多人写代码的时候把 p 数组的索引搞混导致算出来的代价不对。比如矩阵 A1 是 30×35A2 是 35×15那么 p [30, 35, 15]。计算 A1×A2 的代价是 p[0]×p[1]×p[2] 30×35×15。如果你写成 p[1]×p[2]×p[3]那就越界了。排查方法很简单在循环里打印每次计算的 cost然后手动算一遍验证。如果发现某一步的 cost 明显不对大概率就是索引问题。5.2 链长循环的边界条件链长循环的终止条件是 length ≤ n起点的终止条件是 i ≤ n - length 1。这两个边界很容易写错。如果起点循环多跑了一次j 就会超过 n导致数组越界如果少跑了一次某些子问题就不会被计算最终结果可能偏大。我自己的习惯是在写循环之前先在纸上画一个 n4 的小例子把所有的 (i, j) 组合列出来然后对照代码看是否都覆盖到了。这个方法看起来很笨但非常有效尤其是刚学 DP 的时候。5.3 初始值设为无穷大的必要性m[i][j] 在开始枚举分割点之前必须设为一个足够大的值否则第一次比较的时候如果初始值是 0那么任何 cost 都不会小于 0s[i][j] 就不会被更新。用 float(inf) 是最稳妥的做法。如果你用整数要确保这个整数大于所有可能的代价之和。有一个隐蔽的 bug如果你用了一个“看起来很大”的整数比如 10^9但实际代价可能超过这个值比如矩阵维度都是上万级别那就会出错。所以要么用 float(inf)要么根据数据范围估算一个安全的上界。5.4 多个最优解的取舍有时候不同的分割点 k 会产生相同的最小代价。标准算法通常只记录第一个找到的最优 k但实际应用中你可能需要所有最优解或者根据某些额外条件比如内存占用、缓存友好性来选择。这时候就需要修改代码把所有达到最小值的 k 都记录下来。这个需求在编译器优化、查询计划生成等场景中确实存在。如果你只是做算法题记录一个就够了但如果是工程应用最好想清楚是否需要保留多个候选方案。6. 从算法题到工程实践矩阵连乘还能用在哪6.1 数据库查询计划的代价估算数据库在执行多表连接查询时需要决定先连接哪两个表、再连接哪个表。这和矩阵连乘问题在数学结构上几乎一模一样每个连接操作的代价取决于输入表的大小而不同连接顺序的代价差别可能非常大。数据库查询优化器里的 Join Order Selection 问题本质上就是矩阵连乘问题的一个变种。区别在于数据库场景下的代价模型更复杂不只是标量乘法次数还要考虑索引、磁盘 I/O、网络传输等因素。但核心的 DP 框架是一样的定义状态为“连接表 i 到表 j 的最小代价”枚举分割点取最小值。6.2 编译器中的表达式优化编译器在把高级语言翻译成中间代码时需要决定表达式中各个子表达式的计算顺序。对于涉及矩阵运算的表达式不同的计算顺序会导致完全不同的运行时间。一些高性能计算库比如线性代数库在内部就会用类似矩阵连乘 DP 的算法来决定运算顺序。这个场景下的一个额外约束是有些中间结果可能已经被计算过了可以复用。这时候 DP 的状态定义就需要扩展不只是记录最小代价还要记录哪些中间结果可用。这就变成了一个更复杂的优化问题。6.3 实际工程中的简化策略在真实的工程项目中n 通常不会特别大几十到几百O(n³) 的 DP 完全够用。但如果 n 确实很大或者需要实时计算可以考虑一些启发式策略贪心加局部搜索先用贪心得到一个初始解然后用局部搜索优化。虽然不保证最优但速度快结果通常也不错。分治策略把长链分成若干段每段内部用 DP段之间用贪心。这样可以把 O(n³) 降到 O(n²) 甚至更低。查表法如果维度序列的模式比较固定可以预先算好常见情况的解运行时直接查表。这些策略在数据库优化器里都有实际应用。选择哪种取决于你对最优性的要求和对计算时间的容忍度。6.4 一个容易忽略的变种带权矩阵连乘标准问题是所有矩阵同等对待但实际场景中可能有些矩阵的计算代价更高比如稀疏矩阵、特殊结构矩阵。这时候需要在代价函数里加入权重DP 的框架不变只是 cost 的计算方式变了。这个变种在 GPU 计算、分布式计算中很常见因为不同节点的计算能力不同把大矩阵放在慢节点上算显然不划算。如果你遇到这类问题记住核心思路状态定义和转移框架不变只修改代价函数。7. 我踩过的坑与给你的建议第一次学矩阵连乘的时候我花了整整一个下午才搞明白为什么填表顺序要按链长来。当时我按照 i 和 j 的自然顺序填结果怎么都不对打印出来一看很多子问题的值还是初始的 0。后来在纸上画了一个 5×5 的表格手动标出每个格子依赖哪些格子才恍然大悟。如果你正在学这个算法我的建议是不要急着写代码先在纸上把 n4 或 n5 的例子完整推一遍。把 m 表和 s 表都画出来每一步都手动算算完之后再对照代码。这个过程可能花你半个小时但比你对着代码调试两个小时要高效得多。另外一个建议是学完矩阵连乘之后不要就把它扔了。找几道类似的区间 DP 题目练手比如石子合并、多边形三角剖分、最优二叉搜索树。这些问题的 DP 框架和矩阵连乘非常相似都是“枚举分割点合并子问题”。练多了之后你会形成一种直觉看到区间 DP 就知道该怎么定义状态、怎么填表。最后说一个实际编码中的小技巧在写 DP 代码之前先用递归加记忆化的方式写一版。递归版本更直观不容易出错而且能帮你理清状态转移的逻辑。等递归版本跑通了再改写成自底向上的迭代版本。这样即使迭代版本出了问题你也可以用递归版本作为参照来排查。这个方法我在很多 DP 问题上都用过屡试不爽。

矩阵连乘问题：动态规划从原理到工程实践

相关推荐

FFmpeg 转码 DASH/HLS 实战：从踩坑到生产部署

RS485 Modbus组网避坑：多主一从与一主多从怎么选？

两串电池被动均衡方案：MP2642GR-Z与PIC18F87J50实战

更多资讯

Docker Desktop 数据迁移完整流程（Windows 10/11 x64）

Python本地实现横向联邦学习FedAvg全流程

【图像去噪】论文精读：TM-BSN: Triangular-Masked Blind-Spot Network for Real-World Self-Supervised Image Denoisi

YOLO12+A2C2f+DFFN：水果新鲜度检测系统的实战全解析

PyTorch原型网络实战：少样本分类的轻量级方案与代码详解

2S电池组主动均衡系统：ATmega644+MP2642GR-Z设计实战

今日更新

Cephadm实战指南：Linux系统工程师的生产级Ceph集群部署与排障

不想再被 Token 额度卡脖子？把免费 API 接入 WorkBuddy 的完整教程

ITK中SpatialObject几何体系解析：坐标系、变换与管道集成

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？