# week10 note 動態規劃

## 硬幣問題

// 會記錄過程的 Top-down 寫法參考 - by Pudding
#include <iostream>
using namespace std;

const int MAX_CNT = 101;            // 最大金額
const int coin[] = {1, 4, 5};       // 幣值
const int min_coin = coin[0];
int count[MAX_CNT] = {};

int dp(int c) {
    if(c < min_coin || count[c] != 0)
        return count[c];
    int min_ = dp(c - coin[0])+1;
    for(int i = 0; i < N; i++) {
        int tmp = dp(c - coin[i]);
        if(c - coin[i] >= 0 && tmp < min_) {
            min_ = tmp + 1;
        }
    }
    count[c] = min_;
    return min_;
}

int main()
{
    for(int i = 0; i < N; i++) {
        count[coin[i]] = 1;
    }
    for(int i = 0; i <= MAX_CNT; i++) {
        cout << i << " : " << dp(i) << endl;
    }
    system("pause");
    return 0;
}