題目大意：求出共有多少種組合方案，使得數字之和為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 閱讀(409)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃 、
題目分類：遞推/遞歸