UVA 674 -Coin Change

674 - Coin Change

大意：

簡單來說就是你有幣值1,5,10,25,50的5種硬幣，題目會給你7489以內的數字，問你有幾種排列組合的方式 ( 例：10元有 一個10，兩個5，一個5五個1，和十個1 四種，所以答案是4 )

Sample Input 

11
26

Sample Output 

4 

13

解法：

可以想成是背包問題的變形，一次考慮一種硬幣。以第二個範例的26為例：

只考慮一塊錢時，不論多少錢都只有一種換法：
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

多考慮5塊：
1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6
每個可能性=只考慮一塊的可能+五格前的可能性(稍後解釋)

10塊：
1 1 1 1 2 2 2 2 2 4 4 4 4 4 6 6 6 6 6 9 9 9 9 9 12 12
怎麼算的呢？以26塊的12為例：12=6+6
第一個6是只考慮一塊和五塊時，26塊有幾種換法
第二個6是看十格前，也就是考慮1，5，10塊時，16塊有幾種換法
第一個6包含沒有10塊的所有組合，也就是說之後的可能至少要有一個十塊
而26塊至少有一個十塊的換法 = 16塊全部的換法
兩個相加就是答案了~~

25塊和50塊也如法炮製~~要注意的是這題其實只要一次算出1到7489的所有換法，之後題目給什麼數字就可以直接印出答案，不用每次都算一遍喔 QWQ

程式碼：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int coin[5]={1,5,10,25,50};
int bag[7500];

int main()
{
    int num,ans,i,j;
    for(i=0;i<7500;i++){
        bag[i]=1;
    }
    for(i=1;i<5;i++){
        for(j=1;j<7500;j++){
            if(j>=coin[i]){
                bag[j]+=bag[j-coin[i]];
            }
        }
    }
   
    while(scanf("%d",&num)!=EOF){
        ans=bag[num];
        printf("%d\n",ans);
    }
 
   return 0;
}