线性DP
数字三角形
像二维数组一样,设置行和列,只不过这里的列是斜着的,如圈出来的7,坐标可以表示为(4,2)
集合划分,所有路径可以分成俩类,某点左上方一类,右下方一类。
我们先把7去掉,左边计算的就是从起点到8路径的最大值,8的坐标是i-1,j-1,即左边状态可以表示为f[i-1,j-1]含义是从起点走到8这个位置的最大值,最后再给加7
右边计算也同理
f[i,j]=max(左边,右边)
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 510,INF=1e9;
int n, m;
int a[N][N];//a存点
int f[N][N];//f数组表示状态
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
scanf("%d", &a[i][j]);
for (int i = 0; i <= n; i++)
for (int j = 0; j <= i+1; j++)
f[i][j] = - INF;//给状态数组初始化
f[1][1] = a[1][1];//从第一个点走到第一个点的最大值只有一个就是a[1][1]
for (int i = 2; i <= n; ++i)
for (int j = 1; j <= i; j++)
f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);
int res = -INF;
for (int i =2; i <= n; i++)
res = max(res, f[n][i]);
cout << res << endl;
return 0 ;
}
最长上升子序列
该题1 2 5 6严格递增,所以输出是4
我们以第i-1个数来分类,第一个格子0,表示没有第i-1个数,即序列长度是1,之后分别是 i-1是第一个数,i-1是第2个数,i-1是第三个数……倒数第二个数是i-1
由于是上升子序列,aj<ai,aj在ai前面,设最后一个数是ai,倒数第二个数是aj,这样的最大长度上升子序列是f[j]+1,即以j为结尾的最大上升子序列+1
时间复杂度O(N^2)
const int N = 1010;
int n;
int a[N], f[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; i++)
{
f[i] = 1;//f[i]至少为1,即上升子序列只有一个数
for (int j = 1; j < i; j++)//枚举到i的前一个数,所以这里不能是j<=i
if (a[j] < a[i])
f[i] = max(f[i], f[j] + 1);
}
int res = 0;
for (int i = 1; i <= n; i++)
res = max(res, f[i]);
cout << res << endl;
return 0;
}
把上述的最长序列保存下来
const int N = 1010;
int n;
int a[N], f[N],g[N];//g用来保存f[i]是由哪个状态转移来的
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; i++)
{
f[i] = 1;//f[i]至少为1,即上升子序列只有一个数
g[i] = 0;
for (int j = 1; j < i; j++)//枚举到i的前一个数,所以这里不能是j<=i
if (a[j] < a[i])
if(f[i]<f[j]+1)
{
f[i]=f[j]+1;
g[i] = j;//存一下f[i]是由哪个状态转移来的
}
}
int k=1;
for (int i = 1; i <= n; i++)
if (f[k] < f[i])
k = i;//k记录最优解的下标
printf("最大上升子序列长度:%d\n", f[k]);
for (int i = 0, len = f[k]; i < len; i++)
{
printf("%d ", a[k]);
k = g[k];
}
return 0;
}
最长公共子序列问题
这里abd满足条件,所以输出3。
f[i,j]表示的是第一个序列的前i个字母和第二个序列的前j个字母构成的公共子序列。
以a[i]和b[j]是否包含在子序列当中作为划分的依据。a[i]和b[j]选不选共有四种组合情况,我们划分成四个子集,00表示都不选,01不选a[i],选b[j],10选a[i],不选b[j],11俩个都选
00用f[i-1,j-1]来表示,因为f[i,j]没被选,a[i],b[j]没被选
11f[i-1,j-1]+1,去掉最后一组,最后给加回来
中间用f[i-1,j]和f[i,j-1]表示。一般不写00这个状态,因为后面的这些状态里包含该状态。
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main()
{
scanf("%d %d", &n, &m);
scanf("%s%s", a + 1, b + 1);//下标从1开始保存
for(int i=1;i<=n;i++)
for (int j = 1; j <= m; j++)
{
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (a[i] == b[j])
f[i][j] = max(f[i][j], f[i - 1][j - 1]+1);
}
cout << f[n][m] <<endl;
return 0;
}
石子合并
设有N堆石子排成一排,其编号为1,2,3,…,N。
每堆石子有一定的质量,可以用一个整数来描述,现在要将这N堆 石子合并成为一堆。
每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相邻,合并时由于选择的顺序不同,合并的总代价也不相同。
例如有4堆石子分别为 1 3 5 2, 我们可以先合并1、2堆,代价为4,得到4 5 2, 又合并 1,2堆,代价为9,得到9 2 ,再合并得到11,总代价为4+9+11=24;
如果第二步是先合并2,3堆,则代价为7,得到4 7,最后一次合并代价为11,总代价为4+7+11=22。
问题是:找出一种合理的方法,使总的代价最小,输出最小代价。
输入格式
第一行一个数N表示石子的堆数N。
第二行N个数,表示每堆石子的质量(均不超过1000)。
输出格式
输出一个整数,表示最小代价。
数据范围
1≤N≤300
输入样例:
4
1 3 5 2
输出样例:
22
我们以最后一次分界线的位置来分类,可以分成很多类。
含义:左边分一个,左边分2个,左边分3个......一直到k-1个
假设最后合并的是这俩堆,我们可以先将这俩堆去掉,因为无论怎么合并,最后都会合并这俩堆,即去掉最后一步求最大值
左边的最小代价+右边的最小代价+最后一步的代价。
最后一步的代价其实是第i堆到第j堆实际的总重量,最后一堆用前缀和表示为s[j]-s[i-1]。
最终结果从取最小值,k从i枚举到j-1文章来源:https://www.toymoban.com/news/detail-594760.html
时间复杂度:O(N^3)。文章来源地址https://www.toymoban.com/news/detail-594760.html
const int N = 310;
int n;
int s[N];//前缀和
int f[N][N];//状态
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &s[i]);
for (int i = 1; i <= n; i++)
s[i] += s[i - 1];
//按照从小到大枚举所有状态
for(int len=2;len<=n;len++)
for (int i = 1; i + len - 1 <= n; i++)
{
int l = i, r = i + len - 1;//左右端点
//如果只有一堆,和并不需要代价
f[l][r] = 1e9;
for (int k = l; k < r; k++)
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
}
cout << f[1][n] <<endl;
return 0;
}
到了这里,关于第五章——动态规划2的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!