d253: 00674 - Coin Change

題目連結: https://zerojudge.tw/ShowProblem?problemid=d253

# 內容

給你一個金額（ n cents），請你回答共有多少種硬幣組合的方式。例如：n=11，那麼你可以有以下 4 種硬幣的組合：

1. 1 個 10 cent 的硬幣加上 1 個 1 cent 的硬幣
2. 2 個 5 cent 的硬幣加上 1 個 1 cent 的硬幣
3. 1 個 5 cent 的硬幣加上 6 個 1 cent 的硬幣
4. 11 個 1 cent 的硬幣
   p.s 美國的零錢共有以下 5 種硬幣以及其面值：

• penny, 1 cent
• nickel, 5 cents
• dime, 10 cents
• quarter, 25 cents
• half-dollar, 50 cents

請注意：n=0 我們算他是有一種方式。

每當輸入一個 n 值，就輸出有幾種組合

# 解題思路

每一次讀入到一個幣值時，就是將自己本身的組合數加上未加上此貨幣時的組合數，就是新的組合數了
關係式如下: $c[j] = c[j] + c[j-price]$

(像是 01 背包問題，只是全選了)

# 程式碼

#include <iostream>

using namespace std;

int price[5]={1,5,10,25,50};

int c[7500]={};

int n;

int main() {

    c[0]=1;

    for(int i=0;i<5;i++){

        for(int j=price[i];j<7500;j++)

            c[j] += c[j-price[i]];

    }

    while(cin>>n)

        cout<<c[n]<<endl;

}