範例程式碼 uva357

//uva357
#include <iostream>
#include <vector>
using namespace std;

int main(){
    const int MAX = 30000;
    // dp[i] 表示組成 i 分的方法數
    vector<long long> dp(MAX + 1, 0);
    dp[0] = 1;  // 0 分只有 1 種組合：不使用任何硬幣

    // US 硬幣面額：1c, 5c, 10c, 25c, 50c
    int coins[5] = {1, 5, 10, 25, 50};

    // 動態規劃：依序加入每個硬幣，累加組合數
    for (int i = 0; i < 5; i++){
        for (int j = coins[i]; j <= MAX; j++){
            dp[j] += dp[j - coins[i]];
        }
    }
    
    int n;
    // 每行一個測試案例，直到輸入結束
    while(cin >> n){
        if(dp[n] == 1)
            cout << "There is only 1 way to produce " << n << " cents change." << "\n";
        else
            cout << "There are " << dp[n] << " ways to produce " << n << " cents change." << "\n";
    }
    
    return 0;
}