1904 - 拆分数
时间限制 : 1 秒
内存限制 : 32 MB
整数n(n<=120)拆分成1,2,3…n的和，且允许重复，求总共的拆分数。
以4为例：
4=4；
4=3+1；
4=2+2；
4=2+1+1；
4=1+1+1+1；
其中3+1与1+3属于同一种，因此整数4的拆分数有5种。
题目输入
输入包含多个测试用例。每个测试用例包含一个正整数N(1 < = N < = 120),EOF表示输入终止。
题目输出
对于每个测试用例,你必须输出一行包含一个整数P,表明拆分数个数。
输入/输出样例
输入格式
4 10 20
输出格式
5 42 627
C++解答
#include <iostream> using namespace std; int c1[121],c2[121]; int main() { int n,i,j,k; while (cin>>n) { for(i=0;i<=n;i++) c2[i]=0; for(i=0;i<=n;i++) c1[i]=1; for(i=2;i<=n;i++) { for(j=0;j<=n;j++) for(k=0;k+j<=n;k+=i) c2[j+k]+=c1[j]; for(j=0;j<=n;j++) { c1[j]=c2[j]; c2[j]=0; } } cout<<c1[n]<<endl; } return 0; }