357-Let Me Count The Ways

<br /> /* <br /> "Let Me Count The Ways"<br /> Level:5.5<br /> Date:2006/9/30<br /> 技巧:Dynamic programming <br /> 先計算只有1 cent的組合<br /> 再加入5 cent的組合 <br /> 再加入10 cent的組合<br /> 比如17,在1 cent的組合只有一種.<br /> 將5 cent加入考慮後,17=5+12 (12=5+7) (7=5+2) <br /> 原本大家都只有1種,但5cent加入後,7變1+1種 ,12變1+2種 ,17變1+3種 <br /> 所以7有2種,12有3種,17有4種.(有propagate的效應)<br /> 當10 cent加入考慮後,17=10+5<br /> 原本10只有1+2種 ,但10加入後變1+2+1種<br /> 17變4+2種(因為5cent加入後,5變兩種)<br /> 而25或50的加入都只影響大於25或50 的數字,<br /> 所以17共6種. <br /> */<br /> #include <stdio.h><br /> #define N 5<br /> #define M 30002<br /> main(){<br /> int coin[N]={1,5,10,25,50};<br /> long long int table[M]={0};<br /> int cent=0,<br /> i=0,j=0;<br /> <br /> table[0]=1; <br /> for(i=0;i < N;i++){ for(j=coin[i];j < M;j++) table[j]+=table[j-coin[i]]; } while(scanf("%d",¢)==1){ if(table[cent] == 1) printf("There is only 1 way to produce %d cents change.\n",cent); else /*上傳ACM %I64d 要改成 %lld*/ printf("There are %I64d ways to produce %d cents change.\n" 　　　　　　　,table[cent],cent); } }