矩阵连乘—详细讲解
原文来自我的CSDN博客
初次接触dp，就看到很多位大佬给出自己的见解，dp算是最难的算法之一吧，主要在于灵活度高，需要自己推出动态规划方程
- 100个动态规划方程传送门
- 涉及到dp问题那么for循环一般从1开始遍历，这样会好些，虽然目前的我还没理解，但是看到许多大佬写代码都是从1开始遍历，那我也慢慢的改变。
下面我就几个问题来说明一下矩阵连乘问题
矩阵连乘问题-求最优值
题目描述
使用动态规划算法求解矩阵连乘问题，输出最少乘法次数。
输入
每组数据包括两行，第一行为数组长度n，第二行为存储矩阵维数的一维数组。
输出
矩阵连乘最优计算次数。
样例输入
7
30 35 15 5 10 20 25
样例输出
15125
ps:
刚刚开始拿到这个题目的时候，我很懵逼，看不懂题目的意思，所以我就查资料，之后才明白题目的意思，题目给的输入，其实是一个数组，用来存储矩阵的行和列，输出要输出最少乘法运算
通过这个表格我们可以直观地了解题目意思，以及得到许多有用的信息
1. 矩阵的个数等于数组长度减一
2. p[0],p[1]代表第一个矩阵的行数和列数，p[1],p[2]代表第二个矩阵的行数和列数…p[5],p[6]代表第六个矩阵的行数和列数
写代码之前我们要得到状态转移方程方程
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]a[k]a[j]);
我们用三层循环i,j,k分别枚举连乘长度，连乘左边界和划分点
最后这张图片里面应该保存每次长度的最小值，我们先求出长度为2的有多少种情况，然后把最小的填入表格，再依次求3 4 …6;后面一步都要依赖于前面计算的最小值
代码
#include using namespace std; const int maxn = 1e3 + 10; int a[maxn], dp[maxn][maxn]; int main() { int n; while (~scanf("%d", &n)) { for (int i = 0; i n; ++i) //从零开始的遍历 scanf("%d", &a[i]); memset(dp, 0, sizeof(dp)); //首先把整个数组初始化 for (int r = 2; r n; ++r) //枚举连乘长度 { //因为长度为1的矩阵不足以相乘，所以都为0 for (int i = 1; i n - r + 1; ++i) //枚举连乘左边界 { int j = i + r - 1; //枚举连乘又边界 dp[i][j] = dp[i + 1][j] + a[i - 1] * a[i] * a[j]; //其实它是 dp[i][j] =dp[i][i](等于0)+ dp[i + 1][j] + a[i - 1] * a[i] * a[j]; for (int k = i + 1; k j; ++k) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + a[i - 1] * a[k] * a[j]); //从不同位置断开取最小值 } } printf("%d\n", dp[1][n - 1]); //最后只要找到右上角的数字就是所有矩阵相乘的最小值 } return 0; } 大佬一般是从1开始遍历，思路都是一样的，就是一些地方需要改动一下
#include using namespace std; const int maxn = 1e3 + 10; int a[maxn], dp[maxn][maxn]; int main() { int n; while (~scanf("%d", &n)) { for (int i = 1; i n; ++i) scanf("%d", &a[i]); memset(dp, 0, sizeof(dp)); for (int r = 2; r n; ++r) { for (int i = 1; i n - r + 1; ++i) { int j = i + r - 1; dp[i][j] = dp[i + 1][j] + a[i] * a[i + 1] * a[j + 1]; for (int k = i + 1; k j; ++k) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + a[i] * a[k + 1] * a[j + 1]); } } printf("%d\n", dp[1][n - 1]); } return 0; } 简洁明了的代码
#include using namespace std; const int inf = 0x3f3f3f3f; const int maxn = 1e3 + 5; int a[maxn], dp[maxn][maxn]; int main() { int n; while (~scanf("%d", &n)) { memset(dp, 0, sizeof(dp)); for (int i = 1; i n; ++i) scanf("%d", &a[i]); for (int l = 2; l n; ++l) { //枚举连乘长度 for (int i = 1; i + l n; ++i) { //枚举连乘左边界 int j = i + l; //连乘右边界 dp[i][j] = inf; for (int k = i + 1; k j; ++k) { //枚举划分点 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]); } } } printf("%d\n", dp[1][n]); } return 0; } 矩阵连乘问题-构造最优解
题目描述
使用动态规划算法求解矩阵连乘问题。
输入
每组数据包括两行，第一行为数组长度n，第二行为存储矩阵维数的一维数组。
输出
矩阵连乘最优计算次序。
样例输入
7 30 35 15 5 10 20 25
样例输出
A[2:2] * A[3:3] A[1:1] * A[2:3] A[4:4] * A[5:5] A[4:5] * A[6:6] A[1:3] * A[4:6]
多用一个数组储存每一个区间的最优划分点，递归输出
#include using namespace std; const int maxn = 1e3 + 10; const int inf = 0x3f3f3f3f; int a[maxn], dp[maxn][maxn], s[maxn][maxn]; void solve(int l, int r) { if (s[l][r]) //查表递归输出 { solve(l, s[l][r]); solve(s[l][r], r); printf("A[%d:%d] * A[%d:%d]\n", l, s[l][r] - 1, s[l][r], r - 1); } } int main() { int n; while (~scanf("%d", &n)) { for (int i = 1; i n; ++i) scanf("%d", &a[i]); memset(dp, 0, sizeof(dp)); for (int l = 2; l n; ++l) { for (int i = 1; i + l n; ++i) { int j = i + l; dp[i][j] = inf; for (int k = i + 1; k j; ++k) { int x = dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]; if (dp[i][j] > x) { dp[i][j] = x; s[i][j] = k; //记录最优划分点 } } } } solve(1, n); //递归输出 } return 0; } 感觉这个构造法还没理解透，下次理解了再来更新~
#include using namespace std; const int maxn = 1e3 + 10; const int inf = 0x3f3f3f3f; int a[maxn], dp[maxn][maxn], s[maxn][maxn]; void solve(int l, int r) { if (s[l][r]) //查表递归输出 { solve(l, s[l][r]); solve(s[l][r]+1, r); printf("A[%d:%d] * A[%d:%d]\n", l, s[l][r], s[l][r]+1, r); } } int main() { int n; while (~scanf("%d", &n)) { for (int i = 1; i n; ++i) scanf("%d", &a[i]); memset(dp, 0, sizeof(dp)); for (int l = 2; l n; ++l) { for (int i = 1; i + l n; ++i) { int j = i + l-1; dp[i][j] = dp[i + 1][j] + a[i] * a[i + 1] * a[j + 1]; s[i][j] = i; for (int k = i + 1; k j; ++k) { int x = dp[i][k] + dp[k + 1][j] + a[i] * a[k + 1] * a[j + 1]; if (dp[i][j] > x) { dp[i][j] = x; s[i][j] = k; //记录最优划分点打表 } } } } solve(1, n-1); //递归输出 } return 0; }| 爱情不是最初的那份轰轰烈烈满眼是你，还有沉寂下来之后共同面对困难的前行。真爱不是遇见而是培养的————截止今日 |
京公网安备 11010502036488号