UVA 357: Let Me Count The Ways

Q357: Let Me Count The Ways

經過在百貨公司的一場血拼之後，小梅發現她身上的零錢共有17分（cent，美金貨幣單位，其他貨幣及面值請參考下方紅字部分），分別是1個dime，1個nickel，以及2個penny。隔天，小梅去便利商店買完東西後發現她身上的零錢恰好又是17分，這次是2個nickel及7個penny。小梅就在想，有幾種硬幣的組合可能湊成17分呢？經過仔細算算之後，發現共有6種。

你的問題就是：給一個金額，請你回答共有多少種硬幣組合的方式。

p.s 美國的零錢共有以下幾種硬幣以及其面值：

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

Input

每組測試資料1列，有1個整數n（0 <= n <=30000），代表零錢的總金額。

Output

對每組測試資料請輸出共有多少種硬幣組合方式。輸出格式為以下2種其中之一。

• There are m ways to produce n cents change.
• There is only 1 way to produce n cents change.

Sample input

17 
11
4

Sample Output

There are 6 ways to produce 17 cents change. 
There are 4 ways to produce 11 cents change. 
There is only 1 way to produce 4 cents change.

http://luckycat.kshs.kh.edu.tw/homework/q357.htm

import java.util.Scanner;

public class UVA_357 {

 public static void main(String[] args) {
  Scanner sc=new Scanner(System.in);
  int[] coin={1,5,10,25,50};
  long[] m=new long[30001];
  for(int i=0;i<30001;i++)                          //DP演算法
   m[i]=0;
  m[0]=1;
  for(int i=0;i<5;i++){
   for(int j=coin[i];j<=30000;j++){
    m[j]+=m[j-coin[i]];
   }
  }
  while(true){
   int n=sc.nextInt();
   
   /*for(int i=0;i<=n/50;i++){
    for(int j=0;j<=(n-i*50)/25;j++){
     for(int z=0;z<=(n-i*50-j*25)/10;z++){
      for(int x=0;x<=(n-i*50-j*25-z*10)/5;x++){
        m+=(n-i*50-j*25-z*10-x*5)>=0?1:0;
      }
     }
    }
    
   }*/
   
   if(m[n]==1){
    System.out.printf("There is only 1 way to produce %d cents change.\n",n);
   }else{
    System.out.println("There are "+m[n]+" ways to produce "+n+" cents change.");
   }
   
  }

 }

}