【算法】动态规划DP自学笔记 入门：基本知识+经典例题
简述动态规划，是利用历史记录来避免重复计算的一种算法，是求解决策过程最优化的过程。一般用一维数组/二维数组来保存历史记录。一般动态规划有三个步骤：定义数组元素的含义，一般求什么就定义成什么找出数组元素之间的关系式，类似归纳法找出初始值例题1 青蛙跳台阶一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法？由题意知：青蛙可以从n-1的位置到n，也可以从n-2的位置
简述
动态规划，是利用历史记录来避免重复计算的一种算法，是求解决策过程最优化的过程。一般用一维数组/二维数组来保存历史记录。
（将原问题拆解成若干子问题，同时保存子问题的答案，使每个子问题只求解一次，最终获得原问题的答案。）
一般动态规划有三个步骤：
- 定义数组元素的含义，一般求什么就定义成什么
- 找出数组元素之间的关系式，类似归纳法
- 找出初始值
动态规划三要素:重叠子问题、最优子结构、状态转移方程。
理解动态规划可以看：
动态规划详解（修订版）
例题
1 青蛙跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法？
由题意知：青蛙可以从n-1的位置到n，也可以从n-2的位置到n，因此，f(n)=f(n-1)+f(n-2);
初始化：由于变量最小为0,也易得：f(0)=0,f(1)=1,f(2)=2（注意，虽然按照规律，f(2)=f(1)+f(0)=1，但实际并不是这样，要进行特殊处理。）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1005;
int main()
{
int n;cin>>n;
int dp[N];
dp[0]=0,dp[1]=1,dp[2]=2;
for(int i=3;i<=n;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
cout<<dp[n];
return 0;
}
2 斐波那契数列
动态规划算法有两种形式：自顶向下和自底向上
关于动态规划算法的核心和这两种形式的理解：
算法-动态规划 Dynamic Programming–从菜鸟到老鸟
理解完后可以做这道题（个人感觉这是典型的自底向上）：
原题
class Solution {
public:
int fib(int n) {
int a[40];
for(int i=0;i<40;i++) a[i]=-1;
a[0]=0;a[1]=1;
for(int i=2;i<=n;i++)
{
a[i]=a[i-1]+a[i-2];
}
return a[n];
}
};
3 二维数组
原题
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
机器只能向下或向右，因此每个位置只能由其左边或上面得来。
dp[i][j]数组的含义就是走到(i,j)的路径数，转移方程就为：
dp[i][j]=dp[i-1][j]+dp[i][j-1];
初始化：dp[0][0]=0（初始位置）,dp[m][0]=1（第一行的都是1，因为只能从左边得来），dp[0][n]（第一列的都是1，只能从上方得来）。
class Solution {
public:
int uniquePaths(int m, int n) {
int N=105;
int dp[N][N];
dp[0][0]=0;
for(int i=0;i<m;i++)//lie
{
dp[i][0]=1;
}
for(int i=0;i<n;i++)
{
dp[0][i]=1;
}
for(int i=1;i<m;i++)
{
for(int j=1;j<n;j++)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};
4 二维数组
原题
只能向下或向右走，因此每个位置只能由上面或左面走来。
第一行的和第一列的要特殊初始化：只能由前面的和当前位置相加得到。
因此，每个位置的dp值为min(上，左)+该位置的值。
即：
for(int i=1;i<m;i++)
for(int j=1;j<n;j++)
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
AC：
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m=grid.size(),n=grid[0].size();
int dp[m][n];
dp[0][0]=grid[0][0];
//最左边的和最上面的只能由前一个相加得到
for(int i=1;i<n;i++)//最上
{
dp[0][i]=dp[0][i-1]+grid[0][i];
}
for(int i=1;i<m;i++)//最左
{
dp[i][0]=dp[i-1][0]+grid[i][0];
}
//dp
for(int i=1;i<m;i++)
{
for(int j=1;j<n;j++)
{
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
return dp[m-1][n-1];
}
};
5 字符串
求想要将word1转换成word2的最少步骤，那么dp数组的含义就应该是步骤。两个字符串即二维数组。
因此，dp[i][j]的含义是，word1长度为i，word2长度为j时转化使两字符串相同的最少步骤。
然后就应该找其推导关系：
1.当两个字符串都是空串时：dp[0][0]=0;
2.当有一个字符串为空，另一个不为空时，只能进行增/删的步骤,即：
dp[n][0]=n,dp[0][n]=n;
以上两步在初始化阶段完成。
3.串1第i个和串2第j个相同，即不用变化：dp[i][j]=dp[i-1][j-1];
如：
ab ab
i=1,j=1时，都是a，到这一步不用变化，所以dp值跟i-1，j-1的一样。
4.不相同的时候，要做出改变：增，删，改
增：dp[i][j]=dp[i][j-1]
删：dp[i][j]=dp[i-1][j]
改：dp[i][j]=dp[i-1][j-1]
我用画图来表示我的理解：
增：
已有aa，ab，想在aa后加一个b变成aab，即找到串1是aa，串2是a的情况，然后一起加一个b，就变成了aab。
找到串1是aa，串2是a的情况即dp[i][j-1]，加b即再加1，即dp[i][j]=dp[i][j-1]+1；
删：
同理：退到dp[i-1][j]的情况，因为删除步骤要算1，所以共dp[i][j]=dp[i-1][j]+1；
改：
想把ab改为ac，首先ab退回到a，ac退回到a，然后都加c即可。
退回到a的位置的步骤即dp[i][j]，加c即dp[i-1][j-1]+1；
感觉很抽象，理解的但没完全理解…不过[i-1][j],[i-1][j-1],[i][j-1]像是一个套路，不理解记住也行。等我之后完全理解了再来改博客。
代码：
class Solution {
public:
int minDistance(string word1, string word2) {
int len1=word1.size(),len2=word2.size();
int N=505;
int dp[N][N];
//初始化
for(int i=0;i<=len1;i++)
{
dp[i][0]=i;
}
for(int i=0;i<=len2;i++)
{
dp[0][i]=i;
}
//dp
for(int i=1;i<=len1;i++)
{
for(int j=1;j<=len2;j++)
{
if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1];
else dp[i][j]=min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]))+1;
}
}
return dp[len1][len2];
}
};
6 最大连续子序列和
思路：前面的数字不是负数就可以加上。转化为a[i]=max(a[i],a[i]+a[i-1]);
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int a[N];
int main()
{
int n;
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++)
{
if(i>=1) a[i]=max(a[i],a[i]+a[i-1]);
}
int ans=a[0];
for(int i=0;i<n;i++) ans=max(ans,a[i]);
cout<<ans<<endl;
}
return 0;
}
二维
要把二维化成一维。
因为输入是NxN的，所以横着相加和竖着相加是一样的。
其次，想找到最大的子矩阵，要用如下的方法遍历：
图片来源：动态规划-最大子矩阵和（ZOJ 1074 TO THE MAX ）
b数组用来存这一列（列的大小分别为n，n-1，n-2…1）的和，然后再横向求最大子序列和（如上题），即把二维的转换为一维。
三层循环里，第一层是开始的位置，第二层是从开始的位置到最后的遍历，因此第一次循环相当于把整个正方形的数加起来（竖着） ；第三层是相加操作。
出现sum加完还变小了的情况说明前面的为负数，就不相加了。
用ans存下最大的和。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105;
int a[N][N],b[N];
int main()
{
int n;
while(cin>>n)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
}
}
int ans=-999999999;
for(int i=1;i<=n;i++) //i是开始点
{
memset(b,0,sizeof(b));
for(int j=i;j<=n;j++)
{
int sum=0;
for(int k=1;k<=n;k++)
{
b[k]+=a[j][k];//第k列前i到n行的和
sum+=b[k];//相当于一维的最大序列和
if(sum<b[k]) sum=b[k];
if(ans<sum) ans=max(ans,sum);
}
}
}
cout<<ans<<endl;
}
return 0;
}
7 最长递增子序列
拦截导弹
这里是最长下降子序列，但原理是一样的。dp数组的含义是以a[i]作为结尾的最长递减子序列的长度。
双层循环，从头开始算，每一个位置的dp的计算都要遍历前面所有，如果存在小于被比较的数，那么dp就为max(dp[j]+1,dp[i])，即前面符合条件最大的+1；
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=35;
int a[N],dp[N];
int main()
{
int n;cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
dp[0]=1;
for(int i=1;i<n;i++)
{
dp[i]=1;
for(int j=0;j<i;j++)
{
if(a[i]<=a[j]) dp[i]=max(dp[j]+1,dp[i]);
}
}
int ans=-99999999;
for(int i=0;i<n;i++) ans=max(ans,dp[i]);
cout<<ans;
return 0;
}
8 最大上升子序列和问题
dp的含义是以a[i]为结尾的最大上升子序列和。
跟上题思路差不多。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1005;
int a[N],b[N];
int main()
{
int n;cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
b[0]=a[0];
for(int i=1;i<n;i++)
{
int t=a[i];
for(int j=0;j<i;j++)
{
//比前面的大
if(a[i]>a[j]) t=max(t,b[j]+a[i]);
}
b[i]=t;
}
int ans=-1;
for(int i=0;i<n;i++) ans=max(ans,b[i]);
cout<<ans;
return 0;
}
9 最长公共子序列
dp代表的含义：dp[i][j]即到a[i+1] b[j+1]的位置时的最长公共子序列数。
dp[0][n] dp[n][0]都是0.
转移方程：
如果存在a[i+1]==b[j+1] （a的第i个和b的第j个相同）dp[i][j]=dp[i-1][j-1]+1;//前面的情况+1；
如果不存在，那就从前面中选一个最大的赋值。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105;
int dp[N][N];
int main()
{
string a,b;cin>>a>>b;
for(int i=0;i<=b.size();i++) dp[0][i]=0;
for(int i=0;i<=a.size();i++) dp[i][0]=0;
for(int i=1;i<=a.size();i++)
{
for(int j=1;j<=b.size();j++)
{
if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
}
}
cout<<dp[a.size()][b.size()];
return 0;
}
10 01背包问题
一些理解和参考：
动态规划–01背包-详解。
0-1背包(动态规划)
在有限的背包容量内获得最大的价值就是背包问题。
f[i]代表背包内重量为i时的最大价值。内层循环从背包体积开始。
状态转移方程：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}; //二维
f[i]=max(f[i],f[i-v[j]]+val[j]);//一维，减去j物品的重量的加指再加上j物品的价值，内层循环为体积从大到小。
为什么内层循环要从大到小
题大概长成这样。
Bone Collector
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1005;
int dp[N],val[N],v[N];
int main()
{
int t;cin>>t;
while(t--)
{
memset(dp,0,sizeof(dp));
int n,w;cin>>n>>w;
for(int i=0;i<n;i++) cin>>val[i];
for(int i=0;i<n;i++) cin>>v[i];
for(int i=0;i<n;i++)
{
for(int j=w;j>=v[i];j--)//背包体积从大到小
{
dp[j]=max(dp[j],dp[j-v[i]]+val[i]);
}
}
cout<<dp[w]<<endl;
}
return 0;
}
饭卡
当余额大于等于5元时可以买任何东西，那么，我们要在余额要刚好大于5的最后的时候买最贵的东西。
因此，余额为r时，若r>=5,就先让r-=5，因为这先拿掉的5元要用来买最贵的菜。
由于一种菜只能买一次，因此题目转化为余额为r-5和除了最贵的菜的其余菜的背包问题。
dp[i]的含义是，余额为i时可以画的最多的钱。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1005;
int a[N],dp[N];
int main()
{
int n;
while(cin>>n)
{
if(n==0) break;
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++) cin>>a[i];
int r;cin>>r;//rest money
if(r<5)
{
cout<<r<<endl;continue;
}
//可以为负数，说明在最后还剩5元时话这五元去买最贵的菜
sort(a,a+n);
r-=5;
for(int i=0;i<n-1;i++)
{
for(int j=r;j>=a[i];j--)
{
dp[j]=max(dp[j],dp[j-a[i]]+a[i]);//余额还剩j时可以花的最大的钱
}
}
r=r-dp[r]-a[n-1]+5;
cout<<r<<endl;
}
return 0;
}
后面还有一些题和完全背包问题，下次再写。
练习
打家劫舍 II
213. 打家劫舍 II
若抢了第1间就无法抢第n间，因此，范围就改变了：1–n-1，2–n，两次dp比大小即可。
注意范围，若n==1，是无法有dp[2]的（访问非法内存）；
class Solution {
public:
int rob(vector<int>& nums) {
//注意，房间从1开始到n-1
//1~n-2 2~n-1
int n=nums.size();
if(n==1) return nums[0];
int dp[n+1];
dp[0]=0;
int ans=-1;
//1~n-2
dp[1]=nums[0];
for(int i=2;i<=n-1;i++) dp[i]=max(dp[i-1],dp[i-2]+nums[i-1]);
ans=dp[n-1];
dp[2]=nums[1];
dp[1]=0;
for(int i=3;i<=n;i++) dp[i]=max(dp[i-1],dp[i-2]+nums[i-1]);
ans=max(ans,dp[n]);
return ans;
}
};
删除并获得点数
删除并获得点数
做动态规划的题要思考当下的值之前的值有什么关联。此题要求：如果获得3的点数，那就要删除所有2和4，相当于，如果要获得所有3的点数，那就无法获得2的点数。 如此，方程就能写出来了。
如果不要点数i，那么dp[i]==dp[i-1]；
如果要，那就是dp[i]==dp[i-2]+i*i的数量。
dp[i]=max(dp[i-1],dp[i-2]+i*all[i]);
总代码：
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
int n=nums.size(),N=1e4+10;
sort(nums.begin(),nums.end());
int maxn=nums[n-1];
int all[maxn+10];//all[i]表示i的数量
memset(all,0,sizeof(all));
for(int i=0;i<n;i++) all[nums[i]]++;
int dp[maxn+10];//dp[i]表示到数字i的最大点数
memset(dp,0,sizeof(dp));
dp[1]=all[1];
for(int i=2;i<=maxn;i++)
{
dp[i]=max(dp[i-1],dp[i-2]+i*all[i]);
}
int ans=0;
for(int i=1;i<=maxn;i++) ans=max(ans,dp[i]);
return ans;
}
};
跳跃游戏 II
跳跃游戏 II
直接暴力dp：
class Solution {
public:
int jump(vector<int>& nums) {
int n=nums.size();
if(n==1) return 0;
int dp[10005];
memset(dp,0x3f3f3f3f,sizeof(dp));
dp[0]=0,dp[1]=1;
for(int i=2;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(j+nums[j]>=i) dp[i]=min(dp[i],dp[j]+1);
}
}
return dp[n-1];
}
};
然后发现时间1200ms+，这也太拉了，所以优化一下。
可以用贪心+dp的思想，参考这里：别想那么多，就挨着跳吧 II
class Solution {
public:
int jump(vector<int>& nums) {
int n=nums.size();
if(n==1) return 0;
int dp[n];
memset(dp,0,sizeof(dp));
int maxn=0,ans=1,i=0,j=0;
maxn=nums[0];
j=maxn;
while(maxn<n-1)
{
for(int k=i;k<=j;k++)
{
maxn=max(maxn,k+nums[k]);
}
ans++;
i=j+1;j=maxn;
}
return ans;
}
};
环形子数组的最大和
环形子数组的最大和
跟收尾相连的有异曲同工之妙，不过这里有n中形式，n=nums.size();
比如：[1,2,3,-1]就有四种形式，分别是1，2，3，-1开头的。如果全都构造一遍肯定会爆掉。
我在这里使用的方法是：分别求最大连续字串和 和 最小连续字串和，这样即使出现了最大连续字串和需要头几个和尾几个的相连，也可以通过总和减去最小连续字串和得到（也就是说，在正确答案中，总会有最大连续字串和或最小连续字串和的其中一个）。
注意：当全都是负数的时候，会出现sum-minn=0，这样输出的答案为0，是不对的，特判一下即可。
虽然这样的时间和内存都还是很拉，但这种思路很有意思，记录一下。
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int n=nums.size();
int dpmax[n],dpmin[n],sum=0;
memset(dpmax,0,sizeof(dpmax));
memset(dpmin,0,sizeof(dpmin));
dpmax[0]=dpmin[0]=sum=nums[0];
for(int i=1;i<n;i++)
{
dpmax[i]=max(nums[i],dpmax[i-1]+nums[i]);
dpmin[i]=min(nums[i],dpmin[i-1]+nums[i]);
sum+=nums[i];
}
int maxn=-0x3f3f3f3f,minn=0x3f3f3f3f;
for(int i=0;i<n;i++)
{
maxn=max(maxn,dpmax[i]);
minn=min(minn,dpmin[i]);
}
int ans;
//要特判是否全为负数
if(sum==minn) ans=maxn;
else ans=max(maxn,sum-minn);
//cout<<maxn<<" "<<minn;
return ans;
}
};
洛谷P1095 [NOIP2007 普及组] 守望者的逃离
题
一个很巧妙的dp，循环时间。
相当于把两种情况对比，每次选取最优情况，所得到的答案就是两种情况穿插的最优情况。
#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
typedef long long ll;
const int N=1e5+10;
int m,s,t;//魔法，距离，时间
/*
分为只跑步s1和只闪现s2两种情况，留下路程大的
这样正确答案就是跑步和闪现结合的最优
实际上答案就是：先闪现完直到魔力值不够
之后会留下的是max(走路，闪现+恢复)
*/
int main()
{
cin>>m>>s>>t;
int s1=0,s2=0;
fir(i,1,t)//循环时间
{
s1+=17;
if(m>=10)
{
s2+=60;
m-=10;
}
else m+=4;
s1=max(s1,s2);
if(s1>s)
{
cout<<"Yes"<<endl<<i;
return 0;
}
}
cout<<"No"<<endl<<s1;
return 0;
}
洛谷P1064 [NOIP2006 提高组] 金明的预算方案（有依赖的背包问题）
背包问题，有的物品是其他物品的附件。只有买了主件才能买附件。
因此，dp的时候需要考虑：
- 只买主件
- 买主件+附件1
- 买主件+附件2
- 买主件+附件1+附件2
当然，没有附件就只买主件。
当循环到一个附件的时候我们就跳过，因为我们不考虑单独买附件的情况，我们在买此附件的主件的时候会考虑是否买此附件的情况。
代码：
#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
typedef long long ll;
const int N=70,M=4e4;
int w[N],v[N];
int zj[N],zjj[N][3];
int n,m;
int dp[M];//dp[i]表示背包容量为i时的最大价值
int main()
{
cin>>m>>n;
fir(i,1,n)
{
int a,b,c;cin>>a>>b>>c;
w[i]=a;
v[i]=a*b;
if(c==0) //是主件
{
zj[i]=1;
}
else
{
zj[i]=0;
if(zjj[c][1]==0) zjj[c][1]=i;
else zjj[c][2]=i;
}
}
fir(i,1,n)
{
for(int j=m;j>=0;j--)
{
if(zj[i]==0) continue;
if(j>=w[i]) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
//有附件
if(zjj[i][1])
{
//1
if(j>=w[i]+w[zjj[i][1]])
{
dp[j]=max(dp[j],dp[j-w[i]-w[zjj[i][1]]]+v[i]+v[zjj[i][1]]);
}
//2在
if(zjj[i][2])
{
//2
if(j>=w[i]+w[zjj[i][2]])
{
dp[j]=max(dp[j],dp[j-w[i]-w[zjj[i][2]]]+v[i]+v[zjj[i][2]]);
}
//12
if(j>=w[i]+w[zjj[i][1]]+w[zjj[i][2]])
{
dp[j]=max(dp[j],dp[j-w[i]-w[zjj[i][1]]-w[zjj[i][2]]]+v[i]+v[zjj[i][1]]+v[zjj[i][2]]);
}
}
}
}
}
cout<<dp[m];
return 0;
}
洛谷P1941 [NOIP2014 提高组] 飞扬的小鸟（跳台阶和背包的结合）
是跳台阶的背包的结合：
- 每个位置(x,y)都可以从x-1的位置通过点击升上来
- 也可以从x-1的位置因为没有点击而掉下来
- 可以点击多此，因此点击上升是完全背包问题，下降是01背包问题（掉或不掉，点击了就不掉，但是都会遍历到）
- 注意到m的位置就不能再上升，但是可以点击
代码：
#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
typedef long long ll;
const int N=1e4+10;
int n,m,k;//长 高 管道数
int x[N],y[10000+10];//上升和下降
//到m无法上升
/*
到一个位置的方法：
通过多此点击从(i-n,j-n*x)得来（注意每个x不同），点了n次
从上面掉下来，从(i-1,j+y)得来 此时没有点击
*/
int dp[N][1000+10];//dp[i][j]代表到i，j这个坐标的最小点击次数
int gd[N];
struct node
{
int l,h;
}node[N];
int main()
{
cin>>n>>m>>k;
fir(i,0,n-1) scanf("%d%d",&x[i],&y[i]);
fir(i,1,k)
{
int a,b,c;scanf("%d%d%d",&a,&b,&c);
node[a]={b,c};
gd[a]=1;//有管道
}
mem(dp,0x3f);
//小鸟从左边任意高度出发
fir(i,1,m) dp[0][i]=0;
//sort(node+1,node+1+n,cmp);
//dp
int num=0;
fir(i,1,n)
{
//点：向上是完全背包
for(int j=x[i-1]+1;j<=m;j++)//从x[i-1]+1开始
{
dp[i][j]=min(dp[i][j],dp[i-1][j-x[i-1]]+1);
dp[i][j]=min(dp[i][j],dp[i][j-x[i-1]]+1);//也是x[i-1] 相当于在i-1的位置点多次
}
//点到顶了
for(int k=m-x[i-1];k<=m;k++)
{
dp[i][m]=min(dp[i][m],dp[i-1][k]+1);//从左边的顶过来
dp[i][m]=min(dp[i][m],dp[i][k]+1);//从i-1的位置连顶两次
}
for(int j=1;j<=m-y[i-1];j++)
{
dp[i][j]=min(dp[i][j],dp[i-1][j+y[i-1]]);
}
if(gd[i])
{
//不能达到
for(int j=1;j<=node[i].l;j++)
{
dp[i][j]=0x3f3f3f3f;
}
for(int j=node[i].h;j<=m;j++)
{
dp[i][j]=0x3f3f3f3f;
}
// int flag=0;
for(int j=1;j<=m;j++)
{
if(dp[i][j]<0x3f3f3f3f)
{
num++;
break;
}
}
// if(flag) num++;
}
}
int ans=0x3f3f3f3f;
fir(i,1,m)
{
ans=min(ans,dp[n][i]);
}
if(ans<0x3f3f3f3f)
cout<<1<<endl<<ans<<endl;
else cout<<0<<endl<<num<<endl;
}
洛谷P1832 A+B Problem（再升级）
注意：
- 打质数的表里，范围要大一些，不然会RE（打不出题目范围内的质数）
- 初始化是dp[0]=1，因为外面那一层循环的是质数。
#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
typedef long long ll;
const int N=1e5+10;
int n;
int pri[N];
int cnt;
int v[N];
void p()
{
for(int i=2;i<=1e4;i++)
{
if(!v[i])
{
pri[cnt++]=i;
for(int j=2*i;j<=1e4;j+=i) v[j]=1;
}
}
//fir(i,0,cnt-1) szs[pri[i]]=1;
}
ll dp[N];//表示组成这个数的方案数
int main()
{
p();
cin>>n;
dp[0]=1;//这里是精髓
for(int i=0;pri[i]<=n;i++)
{
for(int j=pri[i];j<=n;j++)
{
dp[j]+=dp[j-pri[i]];//由j-pri[i] 和 pri[i] 组成
}
}
cout<<dp[n];
return 0;
}
参考资料和案例来源
前四道题的来源：
告别动态规划，连刷40道动规算法题，我总结了动规的套路
理论参考：
动态规划详解（修订版）
有几道题的来源：
动态规划入门
后面好几道题的来源：
动态规划经典例题汇总 （附最全题目链接）
背包问题的题目：
01背包问题总结
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
10
0- 0
已为社区贡献8条内容
所有评论(0)