d119. 有獎徵答：換零錢

---

解法一、DP

✅ 完整代碼

評分結果(參考) ： AC (4ms, 724KB)

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

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int cash[] = {1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000};
    
    vector<int> dp(50001, 0);
    dp[0] = 1;
    for(int c : cash){
        for(int i=c; i<=50000; i++){
            dp[i] += dp[i-c];
        }
    }
    
    string line;
    while(getline(cin, line)){
        if(line == "0") break;
        
        stringstream ss(line);
        int temp, sum = 0;
        while(ss >> temp){
            sum += temp;
        }
        
        cout << dp[sum]-1 << "\n";
    }
    
    return 0;
}