题目大意：给出1分、5分、10分、25分、50分这5种硬币，求：有多少种方法可以组合成为钱数N。
自我感觉还是比较喜欢记忆化搜索的，一个最大的好处就是不计算不需要的状态，需要多少计算多少！
以下是我的代码：
#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 阅读(963)
评论(1) 编辑 收藏 引用 所属分类:
题目分类：动态规划