前言在算法设计中动态规划是解决多阶段决策最优化问题的核心思想之一而矩阵连乘问题是学习动态规划最经典、最基础的入门例题。本文将从问题分析、核心原理、递归 / 迭代两种实现方式、代码详解、运行结果全维度讲解矩阵连乘问题附带可直接运行的 C 完整代码帮助大家彻底吃透这个经典算法。一、问题背景1. 矩阵乘法规则两个矩阵 Ap×q​ 和 Bq×r​ 相乘结果矩阵 Cp×r​乘法次数为 p×q×r。关键前提只有前一个矩阵的列数 后一个矩阵的行数才能相乘。2. 矩阵连乘问题给定 n 个矩阵A1​,A2​,...,An​其中 Ai​ 的维度为 pi−1​×pi​。求最优的加括号方式使得所有矩阵相乘的总乘法次数最少。✅ 核心目标最小化标量乘法运算次数✅ 算法思想动态规划分解子问题→存储子解→合并最优解二、动态规划核心原理1. 定义状态m[i][j]计算矩阵 连乘的最小乘法次数s[i][j]记录 的最优分割位置 k用于回溯输出加括号方案2. 状态转移方程当 ij单个矩阵m[i][j]0当 ij分割为 和 m[i][j]mini≤kj​{m[i][k]m[k1][j]pi−1​×pk​×pj​}3. 计算顺序递归自顶向下记忆化搜索避免重复计算迭代自底向上按矩阵链长度从小到大计算三、完整 C 代码实现本文提供 递归记忆化和迭代递推两种实现均包含✅ 最小乘法次数计算✅ 最优分割表打印✅ 加括号方案回溯输出#include iostream #include vector #include cstdio using namespace std; // 打印二维vector方便调试查看m表和s表 void Print2Vec(const std::vectorstd::vectorint m) { int row m.size(); int col m[0].size(); printf( ); for (int i 0; i col; i) { printf(%10d, i); } printf(\n); for (int i 0; i row; i) { printf(%3d, i); for (int j 0; j col; j) { printf(%10d, m[i][j]); } printf(\n); } printf(\n--------------------------------------\n); } // 递归实现记忆化搜索 int MatrixChain(const int* p, int i, int j, std::vectorstd::vectorint m, std::vectorstd::vectorint s) { if (i j) { m[i][j] 0; } // 记忆化已经计算过直接返回避免重复递归 else if (m[i][j] 0) { return m[i][j]; } else { // 初始化ki的情况 int k i; m[i][j] MatrixChain(p, k 1, j, m, s) p[i - 1] * p[k] * p[j]; s[i][j] k; // 遍历所有分割点找最小值 for (k i 1; k j; k) { int t2 MatrixChain(p, i, k, m, s) MatrixChain(p, k 1, j, m, s) p[i - 1] * p[k] * p[j]; if (t2 m[i][j]) { m[i][j] t2; s[i][j] k; } } } return m[i][j]; } // 迭代实现自底向上推荐 int MatrixChain2(const int* p, int n, std::vectorstd::vectorint m, std::vectorstd::vectorint s) { if (n 1)return 0; // 单个矩阵乘法次数为0 for (int i 1; i n; i) { m[i][i] 0; } // r为矩阵链长度从2开始 for (int r 2; r n; r) { for (int i 1; i n - r 1; i) { int j i r - 1; // 链的末尾位置 int k i; // 初始化分割点ki m[i][j] m[i][k] m[k 1][j] p[i - 1] * p[k] * p[j]; s[i][j] k; // 遍历所有可能的分割点 for (k i 1; k j; k) { int t1 m[i][k] m[k 1][j] p[i - 1] * p[k] * p[j]; if (t1 m[i][j]) { m[i][j] t1; s[i][j] k; } } } } return m[1][n]; } // 回溯输出最优加括号方案 void Traceback(int i, int j, const std::vectorstd::vectorint s) { if (i j) return; Traceback(i, s[i][j], s); // 左半部分 Traceback(s[i][j] 1, j, s); // 右半部分 cout 相乘A[ i ~ s[i][j] ] 和 A[ s[i][j] 1 ~ j ] endl; } // 主函数 int main() { // 6个矩阵维度数组p长度7 const int n 6; const int p[] { 30,35,15,5,10,20,25 }; // m最小乘法次数表s最优分割点表 std::vectorstd::vectorint m(n 1, std::vectorint(n 1, 0)); std::vectorstd::vectorint s(n 1, std::vectorint(n 1, 0)); // 选择一种实现即可 // int mulMinNum MatrixChain(p, 1, 6, m, s); int mulMinNum MatrixChain2(p, n, m, s); cout 矩阵连乘最小乘法次数 mulMinNum endl; cout endl 最小乘法次数表 m[i][j] endl; Print2Vec(m); cout endl 最优分割点表 s[i][j] endl; Print2Vec(s); cout endl 最优计算顺序 endl; Traceback(1, 6, s); return 0; }四、代码核心模块解析1. 打印函数Print2Vec格式化输出二维数组直观查看最小乘法次数表 m和最优分割表 s方便调试算法执行过程。2. 递归实现MatrixChain自顶向下分解问题用 m[i][j] 存储已计算结果避免重复递归记忆化适合理解动态规划思想效率略低于迭代版3. 迭代实现MatrixChain2推荐自底向上计算按矩阵链长度遍历无递归开销时间复杂度 O(n3)空间复杂度 O(n2)工程中优先使用4. 回溯函数Traceback根据分割表 s[i][j]递归输出最优加括号顺序直观展示先乘哪部分、后乘哪部分。五、运行结果展示输入说明6 个矩阵维度输出结果 矩阵连乘最小乘法次数15125 最小乘法次数表 m[i][j] ...(中间表格省略)... 最优分割点表 s[i][j] ...(中间表格省略)... 最优计算顺序 相乘A[1~1] 和 A[2~2] 相乘A[1~2] 和 A[3~3] 相乘A[4~4] 和 A[5~5] 相乘A[4~5] 和 A[6~6] 相乘A[1~3] 和 A[4~6]✅最终结论6 个矩阵连乘的最小乘法次数为15125六、两种实现方式对比实现方式思路优点缺点适用场景递归记忆化自顶向下代码直观、易理解存在递归调用开销学习、教学迭代递推自底向上效率高、无栈溢出风险代码稍复杂工程、笔试七、总结矩阵连乘是动态规划入门必做题核心是状态定义 状态转移 填表两个关键表m[i][j]存储最小乘法次数s[i][j]存储最优分割点迭代实现效率更高递归实现更易理解回溯函数可以输出最优计算顺序完整解决问题结束语矩阵连乘问题完美体现了动态规划 **“以空间换时间”的核心思想掌握本题后可以轻松拓展学习最长公共子序列、最优二叉搜索树、背包问题 ** 等动态规划经典题型。如果文章对你有帮助欢迎点赞、收藏、关注后续会持续更新算法精讲系列