【題解】CSES 1634 Minimizing Coins

【題目敘述】https://cses.fi/problemset/task/1634/
【解題想法】DP

#include <iostream>
#include <cstring>
using namespace std;
 
int n, x, c[105], dp[1000005];
 
int main() {
    memset(dp, 0x3F, sizeof(dp));
    dp[0] = 0;
    cin >> n >> x;
    for (int i = 0; i < n; i++){
        cin >> c[i];
        for (int j = 0; j+c[i] <= x; j++){
            dp[j+c[i]] = min(dp[j+c[i]], dp[j]+1);
        }
    }
    if (dp[x] > x) cout << -1 << "\n";
    else cout << dp[x] << "\n";
}
分享本文 Share with friends