零钱兑换（动态规划，招商银行FinTech）
参考文章链接：
https://www.cnblogs.com/hapjin/p/5579737.html
题目描述：
牛牛开的银行里一共有n种硬币，第i种硬币价值为vi。
妞妞来到牛牛的银行准备把k元钱兑换为零钱，牛牛想知道一共有多少种零钱兑换方案。例如，牛牛银行有1，2，5三种硬币，k=5，有以下兑换方案：
11111，1112，122，5
所以有4种兑换方案。
输入描述：
输入的第一行为询问数t(1<= t <= 100)。接下来每两行一个测试用例。第一行包含两个整数n和k（1<= n <=100，1<=k <=10000）,表示硬币的种类数和妞妞需要兑换的钱数。第二行n个正整数vi（1<= vi <=200）,表示每种硬币的面值
输出描述：
输出一个整数，表示兑换k元钱的方案数。因为答案方案数可能很大，输出对100000007取模的结果。
示例1
输入：
1
3 5
1 2 5
输出：
4
通过测试代码：
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
long long chargeTypes(vector coinsValues, long long n){
long long m = coinsValues.size();
vector>c;
for(long long i=0;i
{
vectortmp(n+1，0);
c.push_back(tmp);
}
for(long long i = 0; i <=m; i++)
c[i][0] = 1;
for(long long i = 1; i <=n; i++)
c[0][i] = 0;
for(long longi = 1; i <=m; i++)
{
for(long long j = 1; j <=n; j++)
{
if(j < coinsValues[i-1])
{
c[i][j] = c[i-1][j];
continue;
}
c[i][j] = c[i-1][j] + c[i][j - coinsValues[i-1]];//coinsValues下标从0开始
}
}
return c[m][n];
}
long long recursiveChargeTypes(vector coinsValues, long long m, long long n)
{
if(n == 0)
return 1;
if(n < 0)
return 0;
if(m <= 0)
return 0;
else
return recursiveChargeTypes(coinsValues, m-1, n) + recursiveChargeTypes(coinsValues, m, n-coinsValues[m]);
}
int main()
{
int t;
cin>>t;
while(t--)
{
int nn,k;
cin>>nn>>k;
vectorcoinsValues;
long long res=0;
vectorquchong(201,0);
for(long long i=0;i
{
long long tmp=0;
cin>>tmp;
if(quchong[tmp])
{
}
else
{
coinsValues.push_back(tmp);
quchong[tmp]=1;
}
}
sort(coinsValues.begin(),coinsValues.end());
res=chargeTypes(coinsValues, k);
cout<
}
return 0;
}
