1. Toy模板网首页
  2. > Toy博客

动态规划各种背包问题刷题

9月前 作者：什么都不懂的小青蛙 分类：Toy博客 阅读(36) 违法举报

这篇具有很好参考价值的文章主要介绍了动态规划各种背包问题刷题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划

两个约束条件

最优子结构：为了计算考虑了前 i 个物品，总体积为 j 时的最大收益，我们可以先计算考虑了前 i - 1 个物品，总体积为 j 时的最大收益以及考虑了前 i - 1 个物品，总体积为 时的最大收益。知道了考虑了前 i - 1 个物品，总体积为 j 时的最大收益以及考虑了前 i - 1 个物品，总体积为 时的最大收益，我们就能算出考虑了前 i 个物品，总体积为 j 时的最大收益。由于在每次拆解过程中我们会少考虑 1 个物品，最后一定会在有限次拆解后变成一个什么物品都不考虑的子问题，所以在问题拆解过程中不会陷入无限递归。

**无后效性：**我们只关心考虑了前 i 个物品，总体积为 j 时的最大收益，不关心具体哪些物品取了，哪些没取

01背包

01背包的意思是每种物品，只有取不取两种选择，每个物品只能选一次

采用二进制枚举每个取或不取，共 2 n 2^n 2n种方案

复杂度 O ( n 2 n ) O(n2^n) O(n2n)

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    int ans = 0;
    for (int i = 0; i < 1 << n; i++) {
        int totv = 0, totw = 0;
        for (int j = 0; j < n; j++)
            if (i & (1 << j))
                totv += v[j + 1], totw += w[j + 1];
        if (totv <= m)
            ans = max(ans, totw);
    }
    printf("%d\n", ans);
}

my reward:二进制枚举是怎么实现的，首先最外层循环控制每个方案，总共有 2 n 2^n 2n种方案嘛，全不选是0，全选是11111，即 2 n − 1 2^n-1 2n−1。然后内层循环是产生 0    10    100    1000 0\;10\;100\;1000 0101001000这样的二进制数然后一位一位比较过去

dp[N][N]//		第一个参数表示处理到哪个物品，第二个参数表示剩余的容量，整个值表示价值
v[n],w[n]//v表示价值，w表示容量
w// w表示背包的容量
for(int i=1;i<=n;++i){
	for(int j=1;j<=w;++j)
       if(j<w[i]) dp[i][j]=dp[i-1][j];
    else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}

往往这样写会MLE，采取优化，用滚动数组来写，即一维数组

for(int i=1;i<=n;++i){
	for(int j=w;j>=w[i];--j){
	dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    }
}

完全背包

就是不限次数的取

for(int i=1;i<=n;++i){
	for(int j=w[i];j<=w;++j){
	dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    }
}
多重背包

就是每个物品给了 l [ i ] l[i] l[i]个

可以把他当成01背包来做，显然时间复杂度太大了

所以考虑把他分成1 2 4 8 16…

for(int i=1;i<=n;++i){
    int res=l[i];
    for(int k=1;k<=res;k*=2,res-=k)
        for(int j=m;j>=w[i]*k;j--)
            ans[j]=max(ans[j],ans[j-w[i]*k]+v[i]*k);
    for(int j=m;j>=w[i]*res;--j)//最后会剩下个零头，比如res=10  10-1-2-4-3，最后剩个3
        ans[j]=max(ans[j],ans[j-res*w[i]]+v[i]*res);
}
分组背包

每组物品只能选一个

vector<int>c[1001];
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
    scanf("%d%d%d",&a[i],&v[i],&w[i]);
    c[a[i]].push_back(i);
}
for(int i=1;i<=1000;++i){
	for(int j=0;j<=m;++j){
        f[i][j]=f[i-1][j];
        for(auto k : c[i])
            if(v[k]<=j)
                f[i][j]=max(f[i][j],f[i-1][j-v[k]]+w[k]);
    }
}
	printf("%d",f[1000][m]);
区间dp

1.合并石子问题

有 n 堆石子排成一排，第 i 堆石子有 ai 颗，每次我们可以选择相邻的两堆石子合并，代价是两堆石子数目的和，现在我们要一直合并这些石子，使得最后只剩下一堆石子，问总代价最少是多少

#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int a[510],s[510];
int dp[510][510];//dp[i][j]表示i到j的最小代价 
int main(void) {
int n;
cin>>n;
memset(dp,127,sizeof(dp));
for(int i=1;i<=n;++i) {
	cin>>a[i];
	s[i]=s[i-1]+a[i];
}
for(int i=0;i<=n;++i) dp[i][i]=0;//这个初始化不可少哦，因为自己和自己不需要合并
for(int l=1;l<=n-1;++l){
	for(int i=1;i<=n-l;++i){
		int j=i+l;
		for(int k=i;k<j;++k){
		dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);
		} 
	}
} 
cout<<dp[1][n];
return 0;
}

因为求的是最小值，所以初始化成inf，这时就要考虑自身与自身不需要合并的情况，是0

石子合并代表了一类涉及到区间的动态规划问题，其核心思想是按长度从小到大的顺序计算每个区间代表的状态的值。解决这类问题的一般思路就是按上面所说的依次枚举区间长度 l、左端点 i 以及分界线位置 k，然后进行状态的更新和转移

2 有 n 堆石子围成一个圈，第 ii 堆石子有 ai 颗，每次我们可以选择相邻的两堆石子合并，代价是两堆石子数目的和现在我们要一直合并这些石子，使得最后只剩下一堆石子，问总代价最少是多少？

#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int a[510],s[510];
int dp[510][510];//dp[i][j]表示i到j的最小代价 
int main(void) {
int n;
cin>>n;
memset(dp,127,sizeof(dp));
for(int i=1;i<=n;++i) {
	cin>>a[i];
	s[i]=s[i-1]+a[i];
	a[i+n]=a[i];
}
for(int i=n+1;i<=2*n;++i) s[i]=s[i-1]+a[i];
for(int i=0;i<=2*n;++i) dp[i][i]=0; 
for(int l=1;l<2*n;++l){//想不明白为什么是2*n，然后发现n也是对的
	for(int i=1;i<=2*n-l;++i){
		int j=i+l;
		for(int k=i;k<j;++k){
		dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);
		} 
	}
} 
int ans=0x3f3f3f3f;
for(int i=1;i<=n-1;++i){
	ans=min(ans,dp[i][i+n-1]);
}  
cout<<ans;
return 0;
}

这种把序列倍增（两个相同的序列接起来）的思路在解决很多圆上问题的时候非常有用

直接开两层的数组，好像有圆环的话用这种做法挺多的，比如说1234，就开12341234，即可以满足1234 2341 3412 4123这几种不同的合并方式，然后分别对这些不同的序列求最小值，然后求这n种情况的最小值即可

camp 快快变大

#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long 
int a[400];
int dp[400][400],s[400][400]; 
const int mod=1e6+3;
signed main(void) {
int n;
cin>>n;
for(int i=1;i<=n;++i) {
	cin>>a[i];
	s[i][i]=a[i];
}
    //这里的预处理可能可以通过递推来优化一下
for(int i=1;i<=n;++i){
	for(int j=i+1;j<=n;++j){
		s[i][j]=s[i][j-1]*a[j]%mod;
	}
}
for(int len=1;len<=n;++len){
	for(int i=1;i<=n-len;++i){
		int j=len+i;
		for(int k=i;k<j;++k){
			dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+(s[i][k]-s[k+1][j])*(s[i][k]-s[k+1][j]));//考虑最后两堆时，前面合并后的值肯定是前面的乘积（不管合并顺序如何），同理，后一堆也是如此。
		}
	}
}
cout<<dp[1][n];
return 0;
}

要想到不管合并顺序如何，最后的乘积是固定的

也是一道区间dp的题，就是转移后的数会发生变化，所以不会写，建议多看看多理解理解

能量项链

在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为（Mars单位），新产生的珠子的头标记为m，尾标记为n。

需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：
(4⊕1)=1023=60。

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为
((4⊕1)⊕2)⊕3）=1023+1035+10510=710。

#include<iostream>
using namespace std;

int n,head[201],tail[201],f[201][201];
//f[i][j]为起始为i终点为j的链融合生成的最大能量
//head和tail要拓展数组不然越界要考虑模
//珠子 1 2 3 4 5(1) 6(2) 7(3)
//head 1 3 5 7 1 3 5
//tail 3 5 7 1 3 5 7
//没有再考虑4是因为不需要，枚举不到

void read()
{
    int i,j,k,len,max1;
    cin>>n;
    cin>>head[1];
    for(i=2; i<=n; i++)
    {
        cin>>head[i];

        tail[i-1]=head[i];
    }
    tail[n]=head[1];//读入

    for(i=n+1; i<=2*n-1; i++)
    {
        head[i]=head[i-n];
        tail[i]=tail[i-n];
    }//拓展数组

    for(len=1; len<=n; len++)//枚举链长
        for(i=1; i<=2*n-len; i++)//枚举起始位置
        {
            j=i+len;//结束位置

            for(k=i; k<j; k++)//寻找在中间某一位置断开，把两边合并
                f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+head[i]*tail[k]*tail[j]);//这里最后三个相乘的要理解一下哦
            //从i到j的最大能量=max(当前能量，从i到k的最大能量+从k+1到j的最大能量
            //+两颗珠子合并释放的能量)
            //注意我们把i到k，k+1到j看做两颗已经合并的珠子，只需把这两颗合并
        }

    max1=0;
    for(i=1; i<=n; i++)
        if(f[i][n+i-1]>max1)
            max1=f[i][n+i-1];//枚举起始点找最大

    cout<<max1<<endl;

    return;
}

int main()
{
    read();
    return 0;
}
洛谷例题
  1. 最大约数和

选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。

思路：先把不大于s的约数和算出来，把他当作价值。

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int a[1001];
int dp[1001];
void yue(int n){
	for(int i=2;i<=n;++i){
		for(int j=1;j<i;++j){
			if(i%j==0) a[i]+=j;
		}
	}
}
int main(void) {
int n;
cin>>n;
yue(n);
for(int i=1;i<n;++i){
	for(int j=n;j>=i;--j){
		dp[j]=max(dp[j],dp[j-i]+a[i]);
	}
}
cout<<dp[n];
return 0;
}

2.1507 NASA的食物计划

每件食品都有各自的体积、质量以及所含卡路里,在告诉你体积和质量的最大值的情况下,请输出能达到的食品方案所含卡路里的最大值,当然每个食品只能使用一次.

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=60;
int va[N],wb[N],ans[N];
int dp[410][410];
int main(void) {
int v,w,n;
cin>>v>>w>>n;
for(int i=1;i<=n;++i)
cin>>va[i]>>wb[i]>>ans[i]; 
    //先展示三维空间的做法
//for(int i=1;i<=n;++i){
//	for(int j=0;j<=vmax;++j){
//		for(int k=0;k<=wmax;++k){
//			if(j<v[i]||k<w[i]) dp[i][j][k]=dp[i-1][j][k];
//			else dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-v[i]][k-w[i]]+ans[i]);
//		}
//	}
//}
//cout<<dp[n][vmax][wmax];
    
    //二维空间
for(int i=1;i<=n;++i){
	for(int j=v;j>=va[i];--j){
		for(int k=w;k>=wb[i];--k)
		dp[j][k]=max(dp[j][k],dp[j-va[i]][k-wb[i]]+ans[i]);
	}
}
cout<<dp[v][w];
return 0;
}

总结：这也是01背包问题，只是多了一个限制条件而已。

1.小A点菜

题意：有m元，n种，接下来是n种菜品的价格，求能到m元有几种方案

dp[0]=1;//这个初始化很important
int n,m;
int w[104];
cin>>n>>m;
for(int i=1;i<=n;++i)
cin>>w[i];
for(int i=1;i<=n;++i){
	for(int j=m;j>=w[i];--j){
		dp[j]=dp[j]+dp[j-w[i]];//not max这是关键的地方 
	}
}
cout<<dp[m];
//二维写法
void solve(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<=n;++i) dp[i][0]=1;//这里从0开始
	for(int i=1;i<=n;++i) cin>>w[i];
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){//这里从1开始
//			if(j<w[i]) dp[i][j]=dp[i][j]+dp[i-1][j];
//			else dp[i][j]=dp[i][j]+dp[i-1][j-w[i]];
			dp[i][j]+=dp[i-1][j];
			if(j>=w[i]) dp[i][j]+=dp[i-1][j-w[i]];
		}
	}
	cout<<dp[n][m];
}

//用记忆化搜索写的 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL f[105][10005],n,m,v[105],ans;
LL dfs(LL c,LL k)
{
    if(f[c][k])return f[c][k];
    if(v[c]>k)return 0;
    if(v[c]==k)return 1;
    for(LL i=c+1;i<=n;i++)f[c][k]+=dfs(i,k-v[c]);
    return f[c][k];
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(LL i=1;i<=n;i++)scanf("%lld",&v[i]);
    for(LL i=1;i<=n;i++)ans+=dfs(i,m);
    printf("%lld\n",ans);
    return 0;
}

2.集合

题意：把1-n的数分成两个集合，使得两个集合的数之和相等，求方案数

//折半 
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
long long dp[800]={1};//初始化很关键 
int main(void) {
int n;
cin>>n; 
int s=(n*(n+1)/2);
if(s%2==1) cout<<0;//为什么这里return 0就可以过了 
else {
	for(int i=1;i<=n;++i){
		for(int j=s/2;j>=i;--j){
			dp[j]=dp[j]+dp[j-i];
		}
	}
}
cout<<dp[s/2]/2;
return 0;
}

上述两道动态规划都是关于求方案数的题，初始化显得尤为关键

因为当容量为0时也有一个方案，即什么都不装.

3.精卫填海

//把体力当作体积来算，最后再循环遍历，妙啊 
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int dp[10001],vi[10001],w[10001];
int main(void) {
int v,n,c;
cin>>v>>n>>c;
for(int i=1;i<=n;++i){
	cin>>vi[i]>>w[i];
} 
for(int i=1;i<=n;++i){
	for(int j=c;j>=w[i];--j){
		dp[j]=max(dp[j],dp[j-w[i]]+vi[i]);
	}
}
int flag=0;
for(int i=1;i<=c;++i){
	if(dp[i]>=v) {
		cout<<c-i;
		flag=1;
		break;
	}
}
if(!flag) cout<<"Impossible";
return 0;
}



#include<bits/stdc++.h>
using namespace std;
int k[10005],m[10005],f[10005];
int main()
{
	int v,n,c,i,j;
	scanf("%d%d%d",&v,&n,&c);
	for(i=1;i<=n;i++)
		scanf("%d%d",&k[i],&m[i]);
	memset(f,0x7f,sizeof(f));		//初始化
	f[0]=0;					//填0体积木石所需体力为0
	for(i=1;i<=n;i++)
		for(j=v;j>=1;j--)
			if(j<=k[i]||f[j-k[i]]!=0x7f7f7f7f)	//只填第i块就够，如果不够要保证j-k[i]能填满。否则就填不满j体积
                f[j]=min(f[j],m[i]+f[max(0,j-k[i])]);	//max保证下标大于等于0
    if(f[v]<=c)
    	printf("%d",c-f[v]);
    else
    	printf("Impossible");
    return 0;
}

4.神奇的四次方数

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;	
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int dp[N];
int w[22];
void solve() {
	fill(dp, dp + N, inf);
	dp[0] = 0;
	for (int i = 1; i <= 18; ++i) {
	w[i] = pow(i, 4);
	}
	int n;
	cin >> n;
	for (int i = 1; i <= 18; ++i) {
		for (int j = w[i]; j <= n; ++j)
			dp[j] = min(dp[j], dp[j - w[i]] + 1);
	}
	cout << dp[n];
}
int main() {
	solve();
	return 0;
}

总结：这是一个完全背包的问题，求最小值初始化inf，注意dp[0]=0,若没有这个初始条件，就寄了。并不是所有的dp[0]=1，要具体问题具体分析的

1.最长上升子序列问题

常规做法 动态规划

O ( n 2 ) O(n^2) O(n2)

for(int i=1;i<=n;++i){
	for(int j=1;j<i;++j){
	if(a[i]>a[j])
        dp[i]=max(dp[i],dp[j]+1);
    }
}

贪心+二分

O ( n l o g n ) O(nlog_n) O(nlogn​)

#include<iostream>
using namespace std;
// 使用二分法的前提是 数组是已经排好序的（刚好在这里我们的d数组就是递增数组）
//d数组记录的是长度为i的最小的末尾值，末尾越小，成为上升子序列的潜力越大，这就是贪心的思想，d[2]表示长度为2的序列中的末尾的最小值
// 查找返回d数组中第一个比x大的值的下标
int er_method(int a[],int len,int x)
{
    int mid,l=1;
    while(l<=len)
    {
        mid = (l+len)/2;
        if(a[mid]<=x)
            l = mid+1;
        else
            len = mid-1;
    }
    return l;// 此时mid等于l
}
int main()
{
    int n;
    while(cin>>n)
    {
        //待测的数组-------    a
        //存放最长子序列---     d
        //记录最长子序列的长度-- len
        int a[101],d[101],len=1;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        d[1]=a[1];   // 第一个待测数字就d的第一个
        if(n<2)  // 如果待测数字只有一个 ，那就这个数字就是最长子序列
        {
            cout<<1<<endl;
            continue;
        }
        for(int i=2;i<=n;i++)
        {
            if(a[i]>d[len]) // 如果第 i个数大于d数组的最大的数，直接接在d数组的后面
                d[++len] = a[i];
            else    // 比d数组的最大数值小的的话，那就在d数组中找到一个比它大的数，替换掉
                d[er_method(a,len,a[i]] = a[i]; // 这一步不改变d 数组的长度
        }
        cout<<len<<endl;
    }
    return 0;
}

2.最长公共子序列

常规做法 动态规划

O ( n 2 ) O(n^2) O(n2)

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int a[N],b[N],dp[1000][1000];
int main(void) {
int n;
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
 for(int i=1;i<=n;++i) cin>>b[i];
 for(int i=1;i<=n;++i){
 	for(int j=1;j<=n;++j){
 		if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
 		else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);//这是为什么呢
	 }
 }
 cout<<dp[n][n];
return 0;
}

第二种做法

O ( n l o g n ) O(nlog_n) O(nlogn​)

#define _CRT_SECURE_NO_WARNINGS 1
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
int a1[N], a2[N], belong[N];
int b[N], f[N];
int main(void) {
    int n;
    scanf("%d", &n);
    int len = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a1[i]);
        belong[a1[i]] = i;
    }
    for (int i = 1; i <= n; i++)
        scanf("%d", &a2[i]);
    for (int i = 1; i <= n; i++)
    {
        if (belong[a2[i]] > b[len])
        {
            b[++len] = belong[a2[i]];
            f[i] = len;
            continue;
        }
        int k = lower_bound(b + 1, b + len + 1, belong[a2[i]]) - b;
        b[k] = belong[a2[i]];
        f[i] = k;
    }
    printf("%d\n", len);
}

关于为什么可以转化成LIS问题（最长上升子序列），这里提供一个解释。

A:3 2 1 4 5

B:1 2 3 4 5

我们不妨给它们重新标个号：把3标成a,把2标成b，把1标成c……于是变成：

A: a b c d e
B: c b a d e

这样标号之后，LCS长度显然不会改变。但是出现了一个性质：

两个序列的子序列，一定是A的子序列。而A本身就是单调递增的。
因此这个子序列是单调递增的。

换句话说，只要这个子序列在B中单调递增，它就是A的子序列。

哪个最长呢？当然是B的LIS最长。

自此完成转化。

camp

day2

楼梯有 n阶，上楼可以一步上一阶，也可以一步上二阶。

但你不能连续三步都走两阶，计算走到第n阶共有多少种不同的走法。

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
long long int dp[110][3];
void solve(){
	int n;
	long long sum=0;
	cin>>n;
	dp[1][0]=1;
	dp[2][1]=1;
	dp[2][0]=1;
	for(int i=3;i<=n;++i){
		for(int j=0;j<3;++j)
		dp[i][0]=dp[i][0]+dp[i-1][j];
		dp[i][1]=dp[i][1]+dp[i-2][0];
		dp[i][2]=dp[i][2]+dp[i-2][1];
	}
	for(int i=0;i<3;++i) sum+=dp[n][i];
	cout<<sum; 
}
int main(void) {
//int n;
//dp[0]=1;
//dp[1]=1;
//cin>>n;
//for(int i=2;i<=n;++i){
//	dp[i]=dp[i-1]+dp[i-2];
//	if(i>6) dp[i]=dp[i]-dp[i-7];
//	if(i==6) dp[i]--;
//}
//cout<<dp[n];
solve();
return 0;
}

my reward:

1.找规律其实挺难找的，找了n年

2. d p [ i ] [ j ] dp[i][j] dp[i][j]表示走到第i层时连续跳两层了j次 则 d p [ i ] [ 0 ] = d p [ i − 1 ] [ 0 ] + d p [ i − 1 ] [ 1 ] + d p [ i − 1 ] [ 2 ] dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2] dp[i][0]=dp[i−1][0]+dp[i−1][1]+dp[i−1][2] 因为是连续的嘛，所以从上一层跳过来只能跳一层，所以j肯定变为0了。

day3

有一条很长的数轴，一开始你在00的位置。接下来你要走n步，第i步你可以往右走ai或者bi。

问n步之后，0到m的每个位置，能不能走到？

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+5;
int f[110][N];
int a[110],b[110]; 
int main(void) {
int n,m;
f[0][0]=1;
cin>>n>>m;
for(int i=1;i<=n;++i){
	cin>>a[i]>>b[i];
}
for(int i=1;i<=n;++i){
	for(int j=1;j<=m;++j){
		if(j>=a[i]){
			if(f[i-1][j-a[i]]) f[i][j]=1;
		}
		if(j>=b[i]){
			if(f[i-1][j-b[i]]) f[i][j]=1;
		}
	}
}
for(int i=0;i<=m;++i){
	if(f[n][i]) cout<<1;
	else cout<<0;
}
return 0;
}

my reward: f [ i ] [ j ] f[i][j] f[i][j]表示第几步能否走到j，若为1表示能走到，想到其实也挺easy的

一维的怎么写

for(int i=1;i<=n;++i){
	for(int j=m;j>=0;--j){
		int flag=0;
		if(j>=a[i]){
			if(f[j-a[i]]) {
				f[j]=1;
				flag=1;
			}
			else f[j]=0;
		}
		if(j>=b[i]&&flag==0){
			if(f[j-b[i]]) f[j]=1;
			else f[j]=0;
		}
		if(j<a[i]&&j<b[i]) f[j]=0;	
	}
	if(i==1) f[0]=0;
}
for(int i=0;i<=m;++i){
	if(f[i]) cout<<1;
	else cout<<0;

reward：刚开始不开flag，就寄了，因为假如你满足了a，f[j]变成了1，但是你不满足b，f[j]就变回0了

训练赛
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e9 + 7;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s1, s2;
    while (cin >> s1 >> s2) {
        ll i, j, h, a[1001], max = 0;
        for (i = 0; i < s2.size(); i++)a[i] = 0;
        for (i = 0; i < s1.size(); i++) {
            for (j = s2.size() - 1; j >= 0; j--) {
                if (s1[i] == s2[j]) {
                    if (j != 0) a[j] += a[j - 1];
                    else a[j]++;
                    a[j] %= N;
                }
            }
        }
        cout << a[s2.size() - 1] << endl;
    }
    return 0;
}

题目大意

给定n,m,p,q,从（1，1）走到（n,m），只能向右或者向下走，每个点都是0或1，要你求走到右下角的方案数（满足0至少有p，1至少有q）

#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
int dp[2][510][10001];//第三维记录0的个数
int a[510][510];
int n,m,p,q;
init(){
	cin>>n>>m>>p>>q;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>a[i][j];
		}
	}
	dp[1][1][a[1][1]==0]=1;//初始化
}
int main(void){
	int sum=0;
	init();
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(i==1&&j==1) continue;
			for(int k=0;k<=i+j-1;++k){
				if(a[i][j]==1) dp[i%2][j][k]=dp[(i-1)%2][j][k]+dp[i%2][j-1][k];
				else 
				{
					if(k==0) dp[i%2][j][0]=0;
					else dp[i%2][j][k]=dp[i%2][j-1][k-1]+dp[(i-1)%2][j][k-1];	
				}
				dp[i%2][j][k]=dp[i%2][j][k]%mod;
			}
		}
	}
	for(int k=p;k<=n+m-1-q;++k){
		sum=(sum+dp[n%2][m][k])%mod;
	}
	cout<<sum%mod;
	return 0;
}

其实转移方程还是挺好想的，但是会爆内存，于是考虑把第一维降下来，只有0或者1

牛客竞赛网

被3整除的子序列

给你一个长度为50的数字串,问你有多少个子序列构成的数字可以被3整除
答案对1e9+7取模文章来源地址https://www.toymoban.com/news/detail-696361.html

#include <bits/stdc++.h>
using namespace std;
int dp[60][3];
const int mod=1e9+7;
#define int long long 
signed main(void){
    string str;
     getline(cin,str);
    int len=str.size();
    if((str[0]-'0')%3==0) dp[0][0]=1;
    else if((str[0]-'0')%3==1) dp[0][1]=1;
    else if((str[0]-'0')%3==2) dp[0][2]=1;
    for(int i=1;i<len;++i){
            if((str[i]-'0')%3==0) {
                dp[i][0]++;
            dp[i][0]=(dp[i][0]+dp[i-1][0]+dp[i-1][0])%mod;
            dp[i][1]=(dp[i][1]+dp[i-1][1]+dp[i-1][1])%mod;
            dp[i][2]=(dp[i][2]+dp[i-1][2]+dp[i-1][2])%mod;
        }
           else if((str[i]-'0')%3==1){
               dp[i][1]++;
            dp[i][0]=(dp[i][0]+dp[i-1][0]+dp[i-1][2])%mod;
            dp[i][1]=(dp[i][1]+dp[i-1][1]+dp[i-1][0])%mod;
            dp[i][2]=(dp[i][2]+dp[i-1][2]+dp[i-1][1])%mod;
           }
            else if((str[i]-'0')%3==2){
                dp[i][2]++;
            dp[i][0]=(dp[i][0]+dp[i-1][0]+dp[i-1][1])%mod;
            dp[i][1]=(dp[i][1]+dp[i-1][1]+dp[i-1][2])%mod;
            dp[i][2]=(dp[i][2]+dp[i-1][2]+dp[i-1][0])%mod;
       }
    }
    cout<<dp[len-1][0];
    return 0;
}
//dp[i][j]表示前i个余数为j的有几个，那么到第i个，有两种选择，若选i，那么加上dp[i-1][.....],如果不选，那么加上dp[i-1][j]

//稍加优化的版本，就是用一个for循环来代替分类讨论吗
#include <bits/stdc++.h>
using namespace std;
int dp[60][3];
const int mod=1e9+7;
#define int long long 
signed main(void){
    string str;
     getline(cin,str);
    int len=str.size();
    if((str[0]-'0')%3==0) dp[0][0]=1;
    else if((str[0]-'0')%3==1) dp[0][1]=1;
    else if((str[0]-'0')%3==2) dp[0][2]=1;
    for(int i=1;i<len;++i){
          int m=(str[i]-'0')%3;
        dp[i][m]++;
        for(int j=0;j<3;++j){
            dp[i][j]=(dp[i][j]+dp[i-1][j]+dp[i-1][(j+3-m)%3])%mod;
        }
    }
    cout<<dp[len-1][0];
    return 0;
}

到了这里，关于动态规划各种背包问题刷题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 力扣算法刷题Day42｜动态规划：01背包问题 分割等和子集

    力扣题目：01背包问题（二维数组） 刷题时长：参考题解 解题方法：动态规划 + 二维dp数组 复杂度分析 时间 空间 问题总结 理解递推公式困难 本题收获 动规思路：两层for循环，第一层i遍历物品，第二层j枚举背包容量以内所有值 确定dp数组及下标的含义：dp[i][j] 表示从下标

    2024年02月13日
    浏览(59)

  • 力扣算法刷题Day44｜动态规划：完全背包问题 零钱兑换II 组合总和Ⅳ

    力扣题目：#518.零钱兑换II（完全背包组合问题） 刷题时长：7min 解题方法：动态规划（完全背包） 复杂度分析 时间复杂度: O(mn)，其中 m 是amount，n 是 coins 的长度 空间复杂度: O(m) 问题总结 对递推公式的理解 本题收获 题意转换：纯完全背包是凑成背包最大价值是多少，而本

    2024年02月13日
    浏览(39)
  • 贪心算法解决背包问题和动态规划解决0-1背包问题（c语言）

    贪心算法解决背包问题和动态规划解决0-1背包问题（c语言）

    运行结果如下： 运行结果如下： 总结： 贪心算法： 每一步都做出当时看起来最佳的选择，也就是说，它总是做出局部最优的选择。 贪心算法的设计步骤： 对其作出一个选择后，只剩下一个子问题需要求解。 证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安

    2024年02月04日
    浏览(53)
  • 动态规划算法解决背包问题，算法分析与C语言代码实现，时间效率解析

    动态规划算法解决背包问题，算法分析与C语言代码实现，时间效率解析

    🎊【数据结构与算法】专题正在持续更新中，各种数据结构的创建原理与运用✨，经典算法的解析✨都在这儿，欢迎大家前往订阅本专题，获取更多详细信息哦🎏🎏🎏 🪔本系列专栏 -  数据结构与算法_勾栏听曲_0 🍻欢迎大家  🏹  点赞👍  评论📨  收藏⭐️ 📌个人主

    2023年04月16日
    浏览(47)
  • 动态规划01背包问题-代码随想录-刷题笔记

    动态规划01背包问题-代码随想录-刷题笔记

    有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。 每件物品只能用一次 ，求解将哪些物品装入背包里物品价值总和最大。 二维dp数组01背包 确定dp数组以及下标的含义 是使用二维数组，即 dp[i][j] 表示从下标为[0-i]的物品里任意取，

    2024年02月07日
    浏览(56)
  • 算法系列--动态规划--背包问题(1)--01背包介绍

    算法系列--动态规划--背包问题(1)--01背包介绍

    💕\\\"趁着年轻,做一些比较cool的事情\\\"💕 作者：Lvzi 文章主要内容：算法系列–动态规划–背包问题(1)–01背包介绍 大家好,今天为大家带来的是 算法系列--动态规划--背包问题(1)--01背包介绍 背包问题是动态规划中经典的一类问题,经常在笔试面试中出现,是非常 具有区分度 的题

    2024年04月16日
    浏览(50)
  • 算法系列--动态规划--背包问题(3)--完全背包介绍

    算法系列--动态规划--背包问题(3)--完全背包介绍

    💕\\\"Su7\\\"💕 作者：Lvzi 文章主要内容：算法系列–动态规划–背包问题(3)–完全背包介绍 大家好,今天为大家带来的是 算法系列--动态规划--背包问题(3)--完全背包介绍 链接: 完全背包 可以发现完全背包问题和01背包问题还是特比相似的 分析: 完全背包问题 是 01背包问题 的推广

    2024年04月25日
    浏览(41)
  • 【算法-动态规划】0-1 背包问题

    【算法-动态规划】0-1 背包问题

    💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月08日
    浏览(43)
  • 算法学习17-动态规划01：背包问题

    算法学习17-动态规划01：背包问题

    提示：以下是本篇文章正文内容： 提示：这里对文章进行总结： 💕💕💕

    2024年04月27日
    浏览(49)

  • C++ DP算法，动态规划——背包问题（背包九讲）

    有N件物品和一个容量为 V V V 的背包。放入第i件物品耗费的空间是 C i C_i C i ​ ，得到的价值是 W i W_i W i ​ 。 求解将哪些物品装入背包可使价值总和最大。 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即 F [ i , v ] F[i, v] F

    2024年02月16日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包