CSES – Coin Combinations I

題目連結

題意

給 n 個硬幣，問湊出總和 x 有幾種方法，在這題同樣的幾個硬幣不同順序拿會算是不同種方法!

解題想法 – DP

狀態

dp[i] 表示總和為 x 的拿法有幾種

轉移

// c 是儲存硬幣的陣列
for j = 0 ~ n-1:
    dp[i] += dp[i-c[j]]

跟前幾題一樣，我們枚舉最後一個用的硬幣是誰，並且從那個硬幣的 dp 答案轉移過來。

初始條件

dp[0] = 1

總和為 0 的方法有一種，就是都不拿

複雜度: O(n*x)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MOD = 1e9+7;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, x;
    cin >> n >> x; 
    vector <long long> c(n), dp(x+1);
    for(long long &u : c) {
        cin >> u;
    }
    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]])%MOD;
                dp[i] %= MOD;
            }
        }
    }
    cout << dp[x] << '\n';
}