招商銀行（零錢兌換，動态規劃解法）

參考文章連結： 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 <iostream> #include <string> #include <vector> #include <string.h> #include <algorithm> #include <stdio.h> #include <stdlib.h> #include <cstring> #include <queue> #include<list> #include<vector> #include<stdlib.h> #include<iostream> #include<algorithm>

using namespace std; long long chargeTypes(vector<long long> coinsValues, long long n){ long long m = coinsValues.size(); vector<vector<long long>>c; for(long long i=0;i<m+1;i++) {     vector<long long>tmp(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<long long> 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;             vector<long long>coinsValues;             long long res=0;             vector<long long>quchong(201,0);

            for(long long i=0;i<nn;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<<res<<endl;

        }         return 0; }