洛谷P2840 纸币问题 2

P2840 纸币问题 2

---

这题与纸币问题1类似：https://www.cnblogs.com/AAAjiancaipifa/p/19974032
但是dp数组表示的含义改变了
定义dp[i]表示凑出i元的给钱方式数
于是初始条件有了：

dp[0]=1 //凑出0元只有一种方式，就是什么也不给

考虑dp[i]
假设只有一张a元纸币

dp[i]+=dp[i-a] //仅需在原有方式的基础上，加上凑出i-a所需要的方式数.因为在i-a的金额基础上在加上一张a元，方式数不会改变

同理可得对于j种纸币a[1]~a[j]

dp[i]+=dp[i-a[j]]

所以最终的枚举方式:

for(int i=1;i<=w;j++) //枚举金额for(int j=1;j<=n;i++) //枚举纸币面额//一旦金额i小于面额a[j]就可以停止枚举了if(i>a[j]) dp[i]=(dp[i]+dp[i-a[j]])%mod; //记得取模

ACcode:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5,mod=1e9+7;
int n,w;
int a[N];
int dp[N];
int main(){scanf("%d%d",&n,&w);for(int i=1;i<=n;i++) scanf("%d",&a[i]);dp[0]=1;for(int i=1;i<=w;i++)for(int j=1;j<=n;j++)if(i>=a[j]) dp[i]=(dp[i]+dp[i-a[j]])%mod;cout<<dp[w]<<endl;return 0;
}
//Author:AAA_jiancaipifa