复习一场即将寄掉的动规考试时随机抽题抽到的题!![充满希望]

• 首先确定dp数组含义,这里dp[j]含义是凑出面值为j的方案数。
• 其次确定状态转移方程,dp[j] += dp[j - a[i]],即凑出j的方案数加上不加a[i]的方案数。
• 再次是初始化,dp[0]=1,虽然不太有理但是它得等于1。其它的都是0因为要累加。
• 最后是遍历顺序,一层遍历硬币(i),一层遍历背包容量(j)。
• 众所周知,节俭是个好习惯,所以我们的dp数组和a数组只用开10001(确信。但是要开long long!

#include<iostream>
using namespace std;

long long dp[10001],a[10001];//用long long不然会跟我一样寄掉

int main()
{
	int v,n;
	cin >> v >> n;
	for(long long i = 1;i <= v;i++)
	{
		cin >> a[i];
	}
	dp[0] = 1;//初始化
	for(long long i = 1;i <= v;i++)//硬币
	{
		for(int j = a[i];j <= n;j++)//完全背包,所以正序
		{
			dp[j] += dp[j - a[i]];//状态转移方程
		}
	}
	cout << dp[n];//输出dp[n]
	return 0;
}

唉...祈祷明天考试顺利吧!

这是一道简单的背包dp题

这道题要用到背包中的完全背包，如果你要用普通的dfs的话，你只能得到一半的分，那么接下来是dp五步走:

第一步，划分阶段： 以硬币种类和总价值划分

第二步，确定状态变量：$dp[i]$表示有多少种组合能够组出$i$

第三步，确定状态转移方程： $dp[j]$可以通过总价值$j$减去当前硬币的价值$a[i]$得出,也就是 dp[j]=dp[j-a[i]]

第四步，设定边界： 如果总价值为0，也就是没有用硬币，那么有1种组合方式，所以我们设定边界为 dp[0]=1 第五步，ACCODE：

#include<iostream>
using namespace std;
long long v,n,a[26],dp[10001];
int main()
{
	cin>>v>>n;
	for(int i=1;i<=v;i++)
	{
		cin>>a[i];
	}//输入就不说了
	dp[0]=1;//设定边界
	for(int i=1;i<=v;i++)//枚举硬币的种类
	{
		for(int j=a[i];j<=n;j++)//枚举总价值
		{
			dp[j]+=dp[j-a[i]];//状态转移
		}
	}
	cout<<dp[n];//dp[n]表示当总价值为我们要求的n时有多少种组合
    return 0;//完美收尾
}

#include <bits/stdc++.h>
using namespace std;
int v, n, a[100010];
long long dp[100010];
int main(){
	cin >> n >> v;
	for(int i = 1 ; i <= n ; i++){
		cin >> a[i];
	}
	dp[0] = 1;
	for(int i = 1 ; i <= n ; i++){
		for(int j = a[i] ; j <= v ; j++){
			dp[j] += dp[j - a[i]];
		}
	}
	cout << dp[v];
	return 0;
} 

#include<bits/stdc++.h> 
using namespace std;
typedef long long LL;
LL n,m,a[26660],f[10605];
int main()
{
	cin >>n>>m;
	for(int i=1;i<=n;i++)cin >> a[i];
	f[0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=a[i];j<=m;j++)
		{
			f[j]=f[j]+f[j-a[i]];
			//完全背包 
		}
	}
	cout <<f[m]; 
}