题目描述

给定 V 种货币（单位：元），每种货币使用的次数不限。

不同种类的货币，面值可能是相同的。

现在，要你用这 V 种货币凑出 N 元钱，请问共有多少种不同的凑法。

输入格式
第一行包含两个整数 V 和 N。

接下来的若干行，将一共输出 V 个整数，每个整数表示一种货币的面值。

输出格式
输出一个整数，表示所求总方案数。

数据范围
### 1≤V≤25,
### 1≤N≤10000
答案保证在```long long```范围内。

样例

输入样例：
### 3 10
### 1 2 5
输出样例：
### 10

算法1

(计数DP)

这是一个非常明显的计数背包的问题；

而且是无限制计数背包问题

其核心在于->

for(int i = 1;i <= n; i++){
    for(int j = 1;j <= m; j++)
    f[j] += f[j - a[i]] //a[i] 表示 种类（方法）
}

相比于限制类计数背包问题只不过是讲第二个循环### 中的for(int j = 1;j <= m; j ++)改成

for(int j = m; j >= a[i]; j--)

就OK了

C++ 代码

#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
const int maxn=1e4+10;
int v[maxn],f[maxn];
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    f[0]=1;
    for(int i=1;i<=n;++i)    
        scanf("%d",&v[i]);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;j++)
            f[j]+=f[j-v[i]];
    printf("%d\n",f[m]);
    return 0;
}