矩阵链乘法：求最小运算次数 —— 动态规划经典题

题目来源：算法竞赛 / 数据结构与算法课程
难度：中等
核心考点：动态规划、矩阵乘法结合律优化

🧩 题目描述

给定 n 个矩阵，第 i 个矩阵 M_i 的大小为 w_i × w_{i+1}。我们不关心矩阵内容，只关心其维度。

我们需要将这些矩阵按顺序相乘（称为“链乘积”）：

$M = M_1 \times M_2 \times \cdots \times M_n$

由于矩阵乘法满足结合律但不满足交换律，我们可以选择不同的括号化方式来减少总运算次数。

💡 定义：一个 a × b 的矩阵乘以一个 b × c 的矩阵，需要 a × b × c 次标量乘法。

目标：计算将这 n 个矩阵进行链乘积所需的最少运算次数。

📥 输入格式

第一行：一个正整数 n，表示矩阵数量。
第二行：n + 1 个正整数 w_0, w_1, ..., w_n，其中第 i 个矩阵 M_i 的维度是 w_i × w_{i+1}。

📤 输出格式

输出一个整数，代表最小运算次数。

🧪 输入输出样例

输入 #1

3
5 3 2 6

输出 #1

✅ 解析：

矩阵1：5×3，矩阵2：3×2，矩阵3：2×6

方案1：(M1 × M2) × M3 → (5×3×2) + (5×2×6) = 30 + 60 = 90

方案2：M1 × (M2 × M3) → (3×2×6) + (5×3×6) = 36 + 90 = 126

最小值为 90

🧠 算法思路：动态规划（DP）

这是一个经典的区间 DP 问题。

🔹 状态定义

设 dp[i][j] 表示将第 i 个到第 j 个矩阵连乘所需的最小运算次数（1 ≤ i ≤ j ≤ n）。

🔹 状态转移

考虑在区间 [i, j] 中枚举分割点 k（i ≤ k < j），即：

先计算 M_i × ... × M_k，得到一个 w_i × w_{k+1} 的矩阵；
再计算 M_{k+1} × ... × M_j，得到一个 w_{k+1} × w_{j+1} 的矩阵；
最后两者相乘，代价为 w_i × w_{k+1} × w_{j+1}。

因此状态转移方程为：

$dp[i][j] = \min_{i \leq k < j} \left( dp[i][k] + dp[k+1][j] + w_i \times w_{k+1} \times w_{j+1} \right)$

🔹 初始化

当 i == j 时，只有一个矩阵，无需乘法：

$dp[i][i] = 0$

🔹 最终答案

$dp[1][n]$

💻 C++ 实现代码

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> w(n + 1);
    for (int i = 0; i <= n; ++i) {
        cin >> w[i];
    }

    // dp[i][j] 表示从第 i 个矩阵到第 j 个矩阵连乘的最小代价
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

    // 区间长度 len 从 2 开始（至少两个矩阵才能相乘）
    for (int len = 2; len <= n; ++len) {           // len 是当前考虑的矩阵个数
        for (int i = 1; i <= n - len + 1; ++i) {   // 起始位置 i
            int j = i + len - 1;                   // 结束位置 j
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; ++k) {          // 枚举分割点
                int cost = dp[i][k] + dp[k + 1][j] + w[i - 1] * w[k] * w[j];
                if (cost < dp[i][j]) {
                    dp[i][j] = cost;
                }
            }
        }
    }

    cout << dp[1][n] << endl;
    return 0;
}

✅ 注意：这里 w 数组下标从 0 开始，而矩阵编号从 1 到 n，所以：

第 i 个矩阵维度是 w[i-1] × w[i]

因此在状态转移中使用 w[i-1] * w[k] * w[j]

📈 时间复杂度分析

状态数：O(n²)
每个状态转移需枚举 O(n) 个分割点
总时间复杂度：O(n³)
空间复杂度：O(n²)

对于 n ≤ 1000 的数据规模完全可接受。

🧾 手动模拟样例（n=3, w=[5,3,2,6]）

i\j	1	2	3
1	0	5×3×2=30	min{dp[1][1]+dp[2][3]+5×3×6, dp[1][2]+dp[3][3]+5×2×6} = min{0+36+90, 30+0+60} = 90
2	—	0	3×2×6=36
3	—	—	0

✅ 最终结果：dp[1][3] = 90

📌 总结

矩阵链乘法是动态规划入门必学题，掌握它有助于理解区间 DP 和最优子结构。
关键在于正确设置状态和转移方程。
实际应用中可用于优化图形渲染、机器学习中的张量运算等场景。

📎 附录：复制代码按钮（用于网页文章）

如果你将本文发布在支持 HTML 的平台（如掘金、CSDN），可添加以下代码实现“一键复制”功能：

<button onclick="navigator.clipboard.writeText(document.getElementById('code').innerText)">📋 复制代码</button>
<pre id="code">
// 上面的 C++ 代码粘贴在这里
</pre>

📌 欢迎收藏、点赞、转发！
如果你喜欢这类算法题解析，欢迎关注我，后续会持续更新「动态规划系列」、「图论系列」、「字符串处理」等专题！

矩阵链乘法：求最小运算次数 —— 动态规划经典题