学步园

/*
         计算用 1、2、3分的邮票组合成 nNum分有 c1[nNum]种情况 （即 X^nNum的系数为多少）
注意 ！！！：  该代码仅适用于 每种邮票使用次数不限 
         第一个for是：代表 第 i个括号里的多项式 ，第 i个括号代表 i分的邮票情况，即括号中 X^(i的倍数) 
         第二个for，因为从左向右计算，所以每次算完一个括号 就将结果用 c1[]存起来，当再与另一个括号相乘时
		 每次 c1[j]里的系数都加 i，即此时计算所得为X^(j+k)的系数。
		 
		 利用中间数组c2[]的原因是：每次进行括号相乘时，X的系数不是按顺序进行，所以 不能仅用 c1[]完成操作，
		 因为不能保证前一次的计算 c[j+k] 没有改变此时的 c[k]; 
		 
		 参考：  http://www.wutianqi.com/?p=596 

*/
#include<iostream>
using namespace std;
int main()
{
	int c1[1001],c2[1001];
	int nNum;
	while (scanf("%d",&nNum)!=EOF)
	{
		for(int i=0;i<=nNum;i++)  {c1[i]=1;  c2[i]=0; }
		for(int i=2;i<=nNum;i++)
		{
			for(int j=0;j<=nNum;j++)
			{
				for(int k=0;k+j<=nNum;k+=i)
				{
					c2[j+k]+=c1[j];
				}
			}
			for(int j=0;j<=nNum;j++)
			{
				c1[j]=c2[j];
				c2[j]=0;
			}
		}
		printf("%d\n",c1[nNum]);
	}
	return 0;
}



参考博客：  http://www.wutianqi.com/?p=596