题目大意：求出共有多少种组合方案，使得数字之和为n。可以选择的数字有1，5，10，25，50（用数组c存储）。
用d[i][j]表示：使用的最大数字不超过c[j]、和为i的方案总数。考虑这样分类：该方案的最后一个数为c[j]；该方案的最后一个数不为c[j]。那么就有d[i][j]=d[i-c[j]][j]+d[i][j-1]。边界条件为d[0][i]=1。
以下是我的代码：
#include<iostream>
#include<cstdio>
using namespace std;
const int kMaxn(30000);
const int c[]={1,5,10,25,50};
long long d[kMaxn+7][5];
void Init()
{
for(int i=0;i<5;i++)
d[0][i]=1;
for(int i=1;i<=kMaxn;i++)
for(int j=0;j<5;j++)
{
d[i][j]=0;
if(i>=c[j])
d[i][j]+=d[i-c[j]][j];
if(j>=1)
d[i][j]+=d[i][j-1];
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
Init();
int n;
while(scanf("%d",&n)==1)
{
if(d[n][4]<=1)
cout<<"There is only 1 way to produce "<<n<<" cents change."<<endl;
else
cout<<"There are "<<d[n][4]<<" ways to produce "<<n<<" cents change."<<endl;
}
return 0;
}
posted on 2011-05-24 21:14
lee1r 阅读(362)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划 、
题目分类：递推/递归