Uva 674 - Coin Change

解題想法

題目要問的是給定一個金額，請問用{1, 5, 10, 25, 50}來湊的話，共有幾種不同的湊法。

這題其實就是無限背包問題，所以會用到動態規劃的概念。只是把背包的限制重量變成題目欲湊出的金額。物品變成面額。 然後面額的數量沒有限制，隨你喜歡用多少就用多少。

可以分別考慮加上每個面額後，能湊出該金額的方法數會如何變化。 也就是以下的這個轉移式:

dp(金額) += dp(金額 - 當下面額)

如果先考慮一個固定金額，再考慮每加上不同面額，方法數會有甚麼改變(就是把for迴圈內外顛倒)。這樣會造成在考慮方法數的時候會重複計算。

拿十元來舉例

首先加上 $9 的方法數($1 * 9, $5 + $1 * 4)

再加上 $5 的方法數($1 * 5, $5)

會發現 $9 的第二個方法跟 $5 的第一個方法，在分別加上 $1 以及 $5 後會變成相同的方法，這樣就重複計算到了。

程式碼

#include <iostream>
using namespace std;

int main()
{
    int dp[8000] = {1};
    int coins[5] = {1, 5, 10, 25, 50};

    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 8000; j++) {
            if (j - coins[i] >= 0)
                dp[j] += dp[j - coins[i]];
        }
    }

    int money;
    while (cin >> money) 
        cout << dp[money] << endl;

    return 0;
}