P2840 纸币问题 2(动态规划)

题目背景

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

题目描述

你有 n 种面额互不相同的纸币，第 i 种纸币的面额为 ai​ 并且有无限张，现在你需要支付 w 的金额，求问有多少种方式可以支付面额 w，答案对 109+7 取模。
注意在这里，同样的纸币组合如果支付顺序不同，会被视作不同的方式。例如支付 3 元，使用一张面值 1 的纸币和一张面值 2 的纸币会产生两种方式（1+2 和 2+1）。

输入格式

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

输出格式

一行一个整数，表示支付方式的数量。

输入输出样例

输入 #1

6 15
1 5 10 20 50 100

输出 #1

42

输入 #2

3 15
1 5 11

输出 #2

39

说明/提示

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

其实小朋友并不有钱。

思路：

跟上一个版本类似，我们需要将比目标面额小的面额的组成方式找到，这样我们便可得出目标面额的组成方式。我们将dp[i]记为组成面额为i，所需的方案。

注意：我们需要将dp[0]设置为1，因为如果我们现在需要组成面额为5，然后纸币中又恰有5，那么此时dp[5] = dp[5] + dp[0]。dp[0]=1的意义就是，我现在要组成面额为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<ll> dp(w+1,0);dp[0]=1;for(ll i=1; i<=w; i++){for(int j=0; j<n; j++){if(i>=nums[j]) dp[i] = (dp[i] + dp[i-nums[j]])%mod;	}}cout<<dp[w]%mod<<endl;return 0;
}