当前位置：首页 > news >正文

算法详解：矩阵连乘问题（动态规划 C++ 完整实现）

news 2026/4/14 19:17:14

前言

在算法设计中，动态规划是解决多阶段决策最优化问题的核心思想之一，而矩阵连乘问题是学习动态规划最经典、最基础的入门例题。

本文将从问题分析、核心原理、递归 / 迭代两种实现方式、代码详解、运行结果全维度讲解矩阵连乘问题，附带可直接运行的 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. 状态转移方程

当 i=j（单个矩阵）：m[i][j]=0
当 i<j（分割为～和～）：m[i][j]=mini≤k<j{m[i][k]+m[k+1][j]+pi−1×pk×pj}

3. 计算顺序

递归：自顶向下（记忆化搜索，避免重复计算）
迭代：自底向上（按矩阵链长度从小到大计算）

三、完整 C++ 代码实现

本文提供递归（记忆化）和迭代（递推）两种实现，均包含：✅ 最小乘法次数计算✅ 最优分割表打印✅ 加括号方案回溯输出

#include <iostream> #include <vector> #include <cstdio> using namespace std; // 打印二维vector，方便调试查看m表和s表 void Print2Vec(const std::vector<std::vector<int> >& 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::vector<std::vector<int> >& m, std::vector<std::vector<int> >& s) { if (i == j) { m[i][j] = 0; } // 记忆化：已经计算过直接返回，避免重复递归 else if (m[i][j] > 0) { return m[i][j]; } else { // 初始化k=i的情况 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::vector<std::vector<int>>& m, std::vector<std::vector<int>>& 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; // 初始化分割点k=i 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::vector<std::vector<int> >& 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::vector<std::vector<int> > m(n + 1, std::vector<int>(n + 1, 0)); std::vector<std::vector<int> > s(n + 1, std::vector<int>(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

六、两种实现方式对比

实现方式	思路	优点	缺点	适用场景
递归（记忆化）	自顶向下	代码直观、易理解	存在递归调用开销	学习、教学
迭代（递推）	自底向上	效率高、无栈溢出风险	代码稍复杂	工程、笔试