动态规划DP经典例题

一、定义动态规划Dynamic Programming简称 DP一种将答案过程性存储的优化算法。核心就是“空间换时间”通常可以理解为将算过一遍的答案存起来下次计算时直接调用省再次计算的时间。二、最长上升子序列【经典】原题链接​​​​​​https://www.luogu.com.cn/problem/solution/B3637样例2 -4 3 -1 2 -4 3若直接从1-n枚举分别以一号位、二号位..n号位为子序列开头向后枚举找出其中长度max再求和即可。时间复杂度O)几乎不能用。枚举中发现许多数据是重复使用的。例如五号位上的2在枚举二号位时出现了-4-123这种情况枚举四号位时出现了-123这种情况。这时2的最长子序列23重复出现。为了节约时间我们可以在之前算过之后将2的最长子序列用数组存储下来。这样再次枚举到五号位的2时可以直接调用其最长子序列长度省下了计算时间。我们发现一号位最长子序列需要用二、三、四、五、六、七号位的子序列求二号位需要三、四、五、六、七号位子序列三号位要用四、五、六、七号位子序列...以此类推六号位要用七号位子序列七号用自己。可以看出我们只需要从后往前求即先把七号位置子序列求出来再倒推回前面就可以。也就是从后往前求解。#includebits/stdc.h using namespace std; int n,a[5005],dp[5005],ans;//dp存储该点最长上升子序列长度 int main(){ scanf(%d,n); for(int i1;in;i) scanf(%d,a[i]); for(int in;i1;i--){//倒着循环 int cnt0;//用于识别是否存在子序列 //查找i的子序列 for(int ji1;jn;j){//枚举要调用的子序列位置 if(a[i]a[j] dp[i]dp[j]1){//满足上升和最长两个条件 dp[i]dp[j]1;//若满足加上这个点 cnt1; } } if(cnt0)dp[i]1;//不存在子序列 ansmax(ans,dp[i]); } printf(%d,ans); return 0; }三、区间DP1https://www.luogu.com.cn/problem/P1775例题石子合并弱化版依旧从小枚举从小到大枚举合并长度。例如先是两两合并代价接着扩大合并长度枚举三个石堆合并的最小代价四个合并最小代价...n个石堆合并最小代价。在枚举大的石堆代价的时候调用小石堆的代价。因此dp存储i到j的代价即可。详情看注释。#includebits/stdc.h using namespace std; int n,m[305]; int sum[305],dp[305][305];//dp[i][j]i到j合并代价 int main(){ scanf(%d,n); memset(dp,0x3f,sizeof(dp));//因为要取min所以初始化最大值 for(int i1;in;i){ scanf(%d,m[i]); sum[i]sum[i-1]m[i];//前缀和用于求区间和 dp[i][i]0;//自己合并自己代价为0 } for(int l2;ln;l){//合并长度 for(int i1;in-l1;i){ int jil-1;//合并由i到j的石堆 for(int k1;kj;k){ dp[i][j]min(dp[i][j],dp[i][k]dp[k1][j]sum[j]-sum[i-1]); //枚举 i到j的所有合并情况 // sum[j]-sum[i-1]为i到j合并总代价 } } } printf(%d,dp[1][n]); return 0; }四、区间DP2https://www.luogu.com.cn/problem/P1220例题点路灯根据题目不难发现每次人走过时都会顺路关掉一段区间内所有的灯。因此判断是区间DP。我们将所有灯编号走过的区间为l到rl到r之间所有的灯都被关掉了。每一次关灯视为一次行动人一定不是在左边就是在右边。因此每次行动时更新耗电量即可。dp[l][r][k]代表l到r区间的灯被关掉了k0或1代表人处于左端点l或右端点r。每次行动四种情况人现在在左端点要向左走人现在在右端点要向左走人现在在左端点要向右走人现在在右端点要向右走。一次更新即可代码#includebits/stdc.h using namespace std; int n,c,sum[55]; int w[55],dp[55][55][2],x[55];//w为耗电速度x为距离 int calc(int l,int r,int x){ return x*(sum[n]-(sum[r]-sum[l-1]));//计算每次行动消耗的电量 //为每分钟总耗电量-已经关掉的灯耗电量 *时间 } int main(){ scanf(%d%d,n,c); for(int i1;in;i){ scanf(%d%d,x[i],w[i]); sum[i]sum[i-1]w[i];//前缀和求区间和 } memset(dp,0x3f,sizeof(dp));//取min所以初始化最大值 dp[c][c][0]dp[c][c][1]0;//起始点初始化 for(int i1;in;i){//区间长编号 for(int j1;ji-1n;j){//起点编号 int lj,rji-1;//左右端点 for(int k0;k1;k){//枚举四种情况 int vk?r:l;//k0时r,否则l dp[l-1][r][0]min(dp[l-1][r][0],dp[l][r][k]calc(l,r,x[v]-x[l-1])); dp[l][r1][1]min(dp[l][r1][1],dp[l][r][k]calc(l,r,x[r1]-x[v])); } } } printf(%d,min(dp[1][n][0],dp[1][n][1])); return 0; }未完待续