題目大意：求出共有多少種組合方案，使得數(shù)字之和為n。可以選擇的數(shù)字有1，5，10，25，50（用數(shù)組c存儲(chǔ)）。
用d[i][j]表示：使用的最大數(shù)字不超過(guò)c[j]、和為i的方案總數(shù)。考慮這樣分類(lèi)：該方案的最后一個(gè)數(shù)為c[j]；該方案的最后一個(gè)數(shù)不為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;
}