CSES – Coin Combinations II

題目連結

題意

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

解題想法 – DP

狀態

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

轉移

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

這題雖然跟上一題轉移式雖然是一樣的，但是計算的順序有所不同。
因為上一題的計算方法，我們是計算每個 sum 要怎麼湊出來，我們可能會算到同種湊法很多次。

我們現在把枚舉硬幣的迴圈放在外面那層，我們每個硬幣就只會跑一次裡面的迴圈，就可以避免到後面重新使用到這個硬幣。所以這樣就一種湊法就不會被算到第二次了。

我們裡面的迴圈 for i = 1 ~ x 是正著跑。假如 dp[3] 的其中一種方法會用到一個 3 的硬幣，跑到 dp[6] 的時候還是可以用到 dp[6-3] (dp[3])，所以一個硬幣可以被用很多次。

而根據題目這也是合法的，所以這樣我們避免了重複計算，也會處理到同一個硬幣要用很多次的 case。

初始條件

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 j = 0;j < n;j++){
        for(int i = 1;i <= x;i++){
            if(i-c[j] >= 0){
                dp[i] += (dp[i-c[j]])%MOD;
                dp[i] %= MOD;
            }
        }
    }
    cout << dp[x] << '\n';
}