ACM 674 Coin Change

經典DP題。
想了很久，還是想不出個所以然。
雖然看到公式也看到算法，還是不知道為什麼會這樣。
只能說……神奇啊
主要參考兩個網站：
algorithmist跟sagit教學，
公式是長這樣：
c(i,j) = c(i - 1,j) + c(i,j - ai)，
翻成國語是，
有i個元素要加總為j，共有c(i, j)的組合方式，
那麼，c(i, j)會等於i - 1個元素加總為j的組合，再加上i個元素加總為j - ai的組合。
很抽象吧……
舉個例子，
如果有硬幣面額1, 5, 10。
要算出0~26元的所有可能組合方式，
那就從面額1開始填0元到26元的可能，
0 1
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 1
14 1
15 1
16 1
17 1
18 1
19 1
20 1
21 1
22 1
23 1
24 1
25 1
26 1
接著填5，
0 1
1 1
2 1
3 1
4 1
5 2
6 2
7 2
8 2
9 2
10 3
11 3
12 3
13 3
14 3
15 4
16 4
17 4
18 4
19 4
20 5
21 5
22 5
23 5
24 5
25 6
26 6
看出來了嗎？
當只有1元時，所有可能的組合都是1種，
加入5元時，5元到9元的組合變成2(1 + 1)種，
10~14元的組合變成3(1 + 2)種，
對照公式c(i,n) = c(i - 1,n) + c(i,n - ai)，
1元跟5元對n元的組合情況為，
1元對n的組合情況 + 1元跟5元對n - 5元的組合情況！
至於為什麼會這樣呢，看了幾個subset sum的證明，
發現看不是很懂（很數學），所以就先背起來吧，
反正這是正確的……

反正就是每當加入了一個新的面額X元，
要計算n元的組合情況，
就要從之前i - 1個面額對n元的組合情況，加上現在i個面額對n - x元的組合情況。

而起始要從0元開始，0元只有一種情況，
就是什麼都不拿。
1元會從1元開始 + 1，
5元會從5元開始 + 1，
依此類推。

所以若要計算n元，
先把陣列初始為0，陣列[0]設為1，
從面額最小的開始到面額最大的，
依序從該面額開始到n元填入所有的組合情況，
答案就出來了。

重點是從該面額開始到面額n，
然後0元也要考慮，（這樣n -x元若為0才有解）
這裡卡真久，
解釋的不是很好。
sagit的解說滿詳細的，可以看他的。

/* ACM 674 Coin Change
 * mythnc
 * 2011/12/13 13:48:59   
 * run time: 0.036
 */
#include <stdio.h>

#define MAXC 7490
#define COIN 5

void cal(int *);

int main(void)
{
    int ans[MAXC] = { 0 };
    int n;

    cal(ans);

    while (scanf("%d", &n) == 1)
        printf("%d\n", ans[n]);

    return 0;
}

/* cal: pre calculate answer */
void cal(int *ans)
{
    int i, j;
    int money[] = {1, 5, 10, 25, 50};

    ans[0] = 1;
    for (i = 0; i < COIN; i++)
        for (j = money[i]; j < MAXC; j++)
            ans[j] += ans[j - money[i]];
}