初次接触dp，就看到很多位大佬给出自己的见解，dp算是最难的算法之一吧，主要在于灵活度高，需要自己推出动态规划方程
题目描述
使用动态规划算法求解矩阵连乘问题，输出最少乘法次数。
输入
每组数据包括两行，第一行为数组长度n，第二行为存储矩阵维数的一维数组。
输出
矩阵连乘最优计算次数。
样例输入
7
30 35 15 5 10 20 25
样例输出
15125
刚刚开始拿到这个题目的时候，我很懵逼，看不懂题目的意思，所以我就查资料，之后才明白题目的意思，题目给的输入，其实是一个数组，用来存储矩阵的行和列，输出要输出最少乘法运算
通过这个表格我们可以直观地了解题目意思，以及得到许多有用的信息
1. 矩阵的个数等于数组长度减一
2. p[0],p[1]代表第一个矩阵的行数和列数，p[1],p[2]代表第二个矩阵的行数和列数…p[5],p[6]代表第六个矩阵的行数和列数
写代码之前我们要得到状态转移方程方程
我们用三层循环i,j,k分别枚举连乘长度，连乘左边界和划分点
最后这张图片里面应该保存每次长度的最小值，我们先求出长度为2的有多少种情况，然后把最小的填入表格，再依次求3 4 …6;后面一步都要依赖于前面计算的最小值
代码
#include <bits/stdc++.h>
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 <bits/stdc++.h>
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 <bits/stdc++.h>
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 <bits/stdc++.h>
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 <bits/stdc++.h>
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;
}
| 爱情不是最初的那份轰轰烈烈满眼是你，还有沉寂下来之后共同面对困难的前行。真爱不是遇见而是培养的————截止今日 |
|---|