矩阵连乘
高级矩阵连乘是区间 DP 的经典模板。
// 算法讲解
矩阵连乘
输入维度序列，表示 A0(p0×p1), A1(p1×p2), ...
待机
速度 中
待机 ⌨1int matrixChain(vector<int>& p) {
2 int n = p.size() - 1;
3 vector<vector<int>> dp(n, vector<int>(n, 0));
4 for (int len = 2; len <= n; len++)
5 for (int i = 0; i + len - 1 < n; i++) {
6 int j = i + len - 1;
7 dp[i][j] = INT_MAX;
8 for (int k = i; k < j; k++)
9 dp[i][j] = min(dp[i][j],
10 dp[i][k] + dp[k+1][j] + p[i]*p[k+1]*p[j+1]);
11 }
12 return dp[0][n-1];
13}
复杂度分析
时间 O(n³)
空间 O(n²)
最优 O(n³)
最坏 O(n³)
算法讲解
矩阵连乘问题的目标是给 n 个矩阵的乘法加括号，使得总乘法次数最少。
因为矩阵乘法满足结合律，不同的括号方式对应不同的计算代价。
DP 状态 dp[i][j] 表示从第 i 到第 j 个矩阵的最小乘法次数，转移时枚举断点 k。
它属于"区间 DP"类型：大区间的解依赖更小区间的解，通常按区间长度递增枚举。