给定 V 种货币（单位：元），每种货币使用的次数不限。
不同种类的货币，面值可能是相同的。
现在，要你用这 V 种货币凑出 N 元钱，请问共有多少种不同的凑法。
输入格式
第一行包含两个整数 V 和 N。
接下来的若干行，将一共输出 V 个整数，每个整数表示一种货币的面值。
输出格式
输出一个整数，表示所求总方案数。
数据范围
1≤V≤25
1≤N≤10000
答案保证在long long范围内。
输入样例：
3 10
1 2 5
输出样例：
10
难度：简单
时/空限制：1s / 64MB
总通过数：3471
总尝试数：6027
来源：usaco training 2.3
算法标签
DP 背包问题
从题目中我们可以得知，这道题是要我们从v种货币中任意选择凑成n元钱。
运用闫氏DP分析法，这道题的集合表示是从前i种货币中选择搭配出总价值为n的方案的集合，同时这道题要求我们求出数量。在集合划分时我们要做到不重不漏，这样我们将集合划分成两部分，一部分包含第i种货币，即f（i- 1，j），另一部分为包含第i种货币，因为每种货币有无限个，所以可以表示为f(i - 1 , j - w[i] * 1) + f(i - 1 , j - w[i] * 2) + f(i - 1 , j - w[i] * 3) + ……
同时我们不难发现 f(v , j - w[i]) = f(v - 1 , j - w[i]) + f(v - 1 , j - w[i] * 2) + f(v - 1 , j - w[i] * 3) + ……
所以我们就可以得出 f(i , j ) = f（i- 1，j）+ f(i - 1 , j - w[i] * 1) + f(i - 1 , j - w[i] * 2) + f(i - 1 , j - w[i] * 3) + …… = f（i- 1，j）+ f(v , j - w[i]) 。
最后得到的f(v , n) 就是我们想要的答案 。
#include <iostream>
using namespace std ;
int v , n ;
int w[30] ;
long long f[30][10010] ;
int main()
{
cin >> v >> n ;
for(int i = 1 ; i <= v ; i ++)
scanf("%d",&w[i]) ;
f[0][0] = 1 ;//需要特判 i = 0 的情况，用0种货币凑出0元钱的方案为一种 。
for(int i = 1 ; i <= v ; i ++)
{
for(int j = 0 ; j <= n ; j ++)
{
f[i][j] = f[i - 1][j] ;
if(j >= w[i]) f[i][j] += f[i][j - w[i]] ;//当j > w[i]时，才会存在第二种表示的情况
}
}
cout << f[v][n] << endl ;
return 0 ;
}