• 首先确定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;
}