【題解】CSES 1635 Coin Combinations I

#include <iostream>
using namespace std;
 
int n, x, c[105], dp[1000005], mod = 1e9+7;
 
int main() {
    cin >> n >> x;
    for (int i = 0; i < n; i++){
        cin >> c[i];
    }
    dp[0] = 1;
    for (int i = 0; i < x; i++){
        for (int j = 0; j < n; j++){
            if (i+c[j] > x) continue;
            dp[i+c[j]] += dp[i];
            dp[i+c[j]] %= mod;
        }
    }
    cout << dp[x] << "\n";
}