【CSES】1635. Coin Combinations I

題目連結

時間複雜度

• $O(NX)$
• $1\le X\le {10}^6$
  $and$
  $1\le N\le {10}^2$

解題想法

這提示一題偏簡單的 DP 題目，只需要把題目變成

$［i］$ 可以增加

$［i$ + 錢幣面額

$］$ 的可能性就能輕鬆解決了

完整程式

/* Question : CSES 1635. Coin Combinations */

#include<bits/stdc++.h>
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define f first
#define s second

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 1e6 + 50;
const int Mod = 1e9 + 7;
int n, x, cnt;
int coin[MAXN], dp[MAXN];

signed main(){
    opt;
    cin >> n >> x;
    for (int i = 0; i < n; i++) cin >> coin[i];
    
    dp[0] = 1;
    for (int i = 0 ; i < x; i++ ){
        for (int j = 0 ; j < n ; j++ ){
            if ( i + coin[j] > x) continue;
            dp[i + coin[j]] += dp[i];
            dp[i + coin[j]] %= Mod;
        }
    }
    cout << dp[x] << "\n";
}