描述
将一个正整数n表示成一系列正整数之和，n＝n1+ n2+…+ nk(其中，n1≥n2≥…≥nk≥1，k≥1).正整数n的这种表示称为正整数n的划分。正整数n的不同的划分个数称为正整数n的划分数，记作P(n)。
例如，正整数6有如下11种不同的划分，所以P(6)＝11.
6；
5+1；
4+2，4+1+1；
3+3，3+2+1，3+1+1+1；
2+2+2，2+2+1+1，2+1+1+1+1；
1+1+1+1+1+1.
输入
测试文件有多个测试数据，每个测试数据为一个正整数n(1≤n≤100)，占一行。
输出
对每个测试数据计算其划分数P(n)，每个结果占一行。
样例输入
样例输出
提示
算法不能使用简单循环和简单递归算法。
1 #include <stdio.h> 2 int dp[101][101]; 3 int main() 4 { 5 int i,j,n; 6 for(i=0;i<=100;i++) 7 { 8 dp[i][1] = dp[1][i] = dp[0][i] = 1; 9 } 10 for(i=2;i<=100;i++) 11 { 12 for(j=2;j<=100;j++) 13 { 14 if(i>=j) 15 dp[i][j]=dp[i][j-1]+dp[i-j][j]; 16 else 17 dp[i][j]=dp[i][i]; 18 } 19 } 20 while(~scanf("%d",&n)) 21 { 22 printf("%d\n",dp[n][n]); 23 } 24 return 5026; 25 }
原文：http://www.cnblogs.com/jianqian/p/5043438.html