題目大意：給出1分、5分、10分、25分、50分這5種硬幣，求：有多少種方法可以組合成為錢數(shù)N。
自我感覺還是比較喜歡記憶化搜索的，一個最大的好處就是不計算不需要的狀態(tài)，需要多少計算多少！
以下是我的代碼：
#include<stdio.h>
#include<string.h>
#define maxn 7500
const long coin[]={0,1,5,10,25,50};
long n,d[maxn][6];
long dp(long s,long k)
{
if(d[s][k]!=-1) return d[s][k];
d[s][k]=0;
for(long i=k;i<=5&&s>=coin[i];i++)
d[s][k]+=dp(s-coin[i],i);
return d[s][k];
}
int main()
{
memset(d,-1,sizeof(d));
for(long i=0;i<=5;i++) d[0][i]=1;
while(scanf("%ld",&n)==1)
printf("%ld\n",dp(n,1));
return 0;
}
posted on 2010-03-01 19:39
lee1r 閱讀(980)
評論(1) 編輯 收藏 引用 所屬分類:
題目分類：動態(tài)規(guī)劃