UVa OJ - 357 Let Me Count The Ways

The following program is my ACcepted code for UVA-357 .
It's a for everybody to learn and discuss.
If there is any mistake or comment, please let me know.  :D

此乃UVA 357 的AC code!

歡迎一同討論學習，如有錯誤與任何建議請留言 : )

點這裡看題目 Click here to see this Problem!

我之後應該會寫一小篇來解釋這種題目的 DP 思路
但可能要等一小段時間了，如果很想知道的話可以留言，我會趕快寫
I think I will write a small article to explain this problem's DP thought,
but that will in the future some time(?).
If you want to know about that, please leave a commend and I will work on it soon.

因為 n 的index範圍會大到30000
那會讓答案超過int範圍，
所以我使用int int long
如果是UVA 674 Coin Change，就可以使用int
因為他的n值比較小

Because the index range from 1 to 30000,
it will over the int range!
so I used long long int
The UVa 674 Coin Change can be solved when you use int
because its n may be smaller.

//This program is for UVA 357 Let Me Count The Ways
//題目來源 Problem link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=293

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#define MAX 30001
using namespace std;

long long int way[MAX];

int main()
{
    int coin[5] = {1, 5, 10, 25, 50};  
    int n;
 
    while(scanf("%d", &n) != EOF)
    {
        memset(way, 0, sizeof(way));
     
        way[0] = 1;
        for(int i = 0; i < 5; i++)
            for(int j = coin[i]; j <= n; j++)//start from the coin[i] !!!!1
                way[j] = way[j] + way[ j - coin[i]];
     
        if(way[n] == 1)
            printf("There is only 1 way to produce %d cents change.\n", n);
        else
            printf("There are %lld ways to produce %d cents change.\n", way[n], n);
    }
 
    return 0;
}

Please feel free to use it after adding this blog as an reference. (http://autekroy.blogspot.tw) If there is any mistake or comment, please let me know. :D 

歡迎使用與分享任何內容，但請記得標示此部落格為出處。(http://autekroy.blogspot.tw/) 如果有發現任何的錯誤與建議請留言或跟我連絡。 : )