跳至主要内容

Coin Combinations I

題目​

有 nn 種幣值，有幾種排列可以湊出 xx 元 ?

輸入​

第一行有兩個整數 nn 和 xx，分別代表幣值的數量以及目標要湊出多少錢。

第二行有 nn 個相異正整數 cic_i，代表每種幣值。

  • （1≤n≤1001 \le n \le 100）
  • （1≤x≤1061 \le x \le 10^6）
  • （1≤ci≤1061 \le c_i \le 10^6）

輸出​

求有幾種排列可以湊出 xx 元，並輸出答案模 109+710^9+7 的值

範例測資​

Input:
3 9
2 3 5

Output:
8
  • 2+2+52 + 2 + 5
  • 2+5+22 + 5 + 2
  • 5+2+25 + 2 + 2
  • 3+3+33 + 3 + 3
  • 2+2+2+32 + 2 + 2 + 3
  • 2+2+3+22 + 2 + 3 + 2
  • 2+3+2+22 + 3 + 2 + 2
  • 3+2+2+23 + 2 + 2 + 2

總共 88 種

想法​

舉個例子，假設有其中一種幣值為 55，且要湊出 1212 元，那麼我們可以得知湊出 1212 元的方法是湊出 1212 的方法數加上湊出 77 元的方法數

狀態定義​

設 dpjdp_{j} 的狀態為湊出 jj 元的排列數

狀態轉移​

枚舉每一種幣值，若能夠湊出 j−cij - c_i 元，那麼可以推得轉移式為 dpj=dpj−c1+dpj−c2+...+dpj−cndp_{j} = dp_{j - c_1} + dp_{j - c_2} + ... + dp_{j - c_n}，因為我們可以花 cic_i 元讓金額從 j−cij - c_i 變成 jj ，

Note 1: 注意 j−cij - c_i 是否小於 00

Note 2: 初始狀態為 dp0=0dp_{0} = 0，因為湊出總合為 00 需要 00 個硬幣

Note 3: 因為我們先枚舉要湊出來的錢，再枚舉每一種幣值，所以算出來的是硬幣的排列數而不是組合數

範例程式碼​

C++ 範例 
#include<bits/stdc++.h>
#define int long long
#define IO ios_base::sync_with_stdio(0),cin.tie(0)
const int MOD = 1e9+7;
using namespace std;

signed main() {
    IO;
    int n, x;
    cin >> n >> x;
    vector<int>c(n);
    vector<int>dp(x + 1, 0);
    for(int i = 0; i < n; i++) {
        cin >> c[i];
    }
    dp[0] = 1;
    for(int i = 1; i <= x; i++) {
        for(int j = 0; j < n; j++) {
            if(i - c[j] >= 0) {
                dp[i] += dp[i - c[j]];
                dp[i] %= MOD;
            }
        }
    }
    cout << dp[x];
}