CSES – Minimizing Coins

題目連結

題意

給 n 個硬幣 (硬幣面額都是正整數)，問最少花幾個硬幣就可以湊出總和 x (一個硬幣可以重複使用)

狀態

dp[i] 表示湊出總合為 i 的最少硬幣數

轉移

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

對於每個 i ，我們枚舉上一個拿的是哪個硬幣。
枚舉到 c[1] 的話，代表是從 dp[i-c[1]] 轉移過來，加上 1 代表多拿這個硬幣。
…. 以此類推

每次都取比較小的那個值就可以了

初始條件

dp[0] = 0

要拿到總合為 0 就是不拿，所以是 0 硬幣數

複雜度: O(n*x)

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    long long n, x;
    cin >> n >> x;
    vector <long long> c(n), dp(x+1,INT_MAX);
    for(long long &a : c) cin >> a;
    dp[0] = 0;
    for(int i = 1;i <= x;i++){
        for(int j = 0;j < n;j++){
            if(i-c[j] >= 0){
                dp[i] = min(dp[i], dp[i-c[j]]+1);
            }
        }
    }
    if(dp[x] == INT_MAX) cout << "-1\n";
    else cout << dp[x] << '\n';
}