题目背景

你是一个非常有钱的小朋友。

注意： 本题和《进阶篇》的对应题目，输入格式略有差异。

题目描述

你有 n 种面额互不相同的纸币，第 i 种纸币的面额为 ai​ 并且有无限张，现在你需要支付 w 的金额，请问有多少种纸币组合能恰好支付金额 w，答案对 109+7 取模。

输入格式

第一行两个正整数 n,w，分别表示纸币的种数和要凑出的金额。
第二行一行 n 个以空格隔开的正整数 a1​,a2​,…an​ 依次表示这 n 种纸币的面额。

输出格式

一行一个整数，表示能恰好凑齐面额 w 的纸币组合数量。

输入输出样例

输入 #1

6 15
1 5 10 20 50 100

输出 #1

6

输入 #2

3 15
1 5 11

输出 #2

5

说明/提示

对于 40% 的数据，满足 n≤10，w≤100；
对于 100% 的数据，满足 1≤n≤103，1≤ai​≤w≤104。

其实小朋友并不有钱。

思路：

和纸币问题2不同的是，现在顺序是重要的，即我们不能像版本2中那样先遍历金额再遍历面额，而得先遍历面额再遍历金额，接下来介绍两者的不同之处：

先遍历金额再遍历面额：这种方式会将目标金额的最后一张纸币设为任何一个面额，例如：假设我需要组成3，但是面额中有1，2。那由于我们会将1，2都遍历到，所以会产生（1，2），（2，1）

这样就产生了重复。

先遍历面额再遍历金额：为什么说这种方式可以去重呢？因为我们先对面额进行遍历，这样就保证了面额的固定顺序，例如：如果我们以1，2的方式遍历，那么最后组成3，只有可能是（1，2）。

即对于每一种面额，我们会遍历所有金额，计算出每一种金额所需要使用此面额的数量，之后我们便会处理下一种面额，从而达到了去重（又叫强制固定了顺序）。

我们再来谈谈实现：

由于需要考虑到不用当前面额；以及使用当前面额；这是两个维度，需要使用二维数组。对于使用当前面额这种情况，意味着最后一张是当前面额，也就是说需要考虑到当前金额减这个面额。

我们定义dp[i][j]为当前来到了i面额，需要构成j金额的方式数。

对于边界情况，我们定义dp[i][0]为0，这意味着，来到i面额，我们构成金额0所需要的方式数为1，也就是不使用任何纸币这一种方式。

实际上，只需要定义dp[0][0]为0，然后每次从金额0开始遍历就可以，因为题目规定了面额一定大于0，那么每次金额为0时，我们只能选择不采用当前面额为最后一张纸币，所以这样的话，dp[1][0]，dp[2][0]，dp[3][0]......就都会为0了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

typedef struct Group{
	int x,y;
	bool operator<(Group g) const{
		if(x!=g.x) return x<g.x;
		else return y<g.y;
	}	
}G;
const ll mod = 1e9+7;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	ll n,w;
	cin>>n>>w;
	vector<ll> nums;
	for(int i=0; i<n; i++){
		ll t;
		cin>>t;
		nums.push_back(t);
	}
	
	vector<vector<int>> dp(n+1,vector<int>(w+1,0));
//	cout<<1<<endl;
	dp[0][0] = 1;
	for(int i=1; i<=n; i++){
		for(int j=0; j<=w; j++){
			dp[i][j] = dp[i-1][j];
			if(j>=nums[i-1]) dp[i][j] = (dp[i-1][j]%mod + dp[i][j-nums[i-1]]%mod)%mod;
//			cout<<dp[i][j]<<" ";
		}
//		cout<<endl;
	}
	
	
	
	cout<<dp[n][w]%mod<<endl;
	return 0;
}

还没结束哦，我们再来谈谈优化：

实际上，我们并不需要二维数组，我们会发现，在来到每一个面额，我们在此面额下的每个金额的组成方式只与使用前一个面额的状态有关，要么就是不使用当前面额来组成当前金额（当前金额小于这个面额），要么就是不使用当前面额以及使用当前面额，来组成当前金额（当前金额不小于这个面额）。

所以我们只需要每次直接对dp[j]进行修改即可，j为每个金额。

进一步，我们可以将内层循环进行改进，每次从当前面额一直遍历到目标金额，因为小于当前面额的话，就不会对上一次做出任何改变。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

typedef struct Group{
	int x,y;
	bool operator<(Group g) const{
		if(x!=g.x) return x<g.x;
		else return y<g.y;
	}	
}G;
const ll mod = 1e9+7;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	ll n,w;
	cin>>n>>w;
	vector<ll> nums;
	for(int i=0; i<n; i++){
		ll t;
		cin>>t;
		nums.push_back(t);
	}
	
//	vector<vector<int>> dp(n+1,vector<int>(w+1,0));
	vector<int> dp(w+1,0);

//	cout<<1<<endl;
//	dp[0][0] = 1;
	dp[0] = 1;
	for(int i=1; i<=n; i++){
		for(int j=nums[i-1]; j<=w; j++){
//			dp[i][j] = dp[i-1][j];
//			if(j>=nums[i-1]) dp[i][j] = (dp[i-1][j]%mod + dp[i][j-nums[i-1]]%mod)%mod;
			dp[j] = (dp[j]%mod + dp[j-nums[i-1]]%mod)%mod;		
//			cout<<dp[i][j]<<" ";
		}
//		cout<<endl;
	}
	
	
	cout<<dp[w];
//	cout<<dp[n][w]%mod<<endl;
	
	return 0;
}