引自：http://www.cnblogs.com/DwyaneTalk/p/4617057.html
华师大oj 1009
问题描述：
将正整数n表示成一系列正整数之和：n=n1+n2+…+nk， 其中n1≥n2≥…≥nk≥1，k≥1。 正整数n的这种表示称为正整数n的划分。求正整数n的不 同划分个数。
例如正整数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。
输入：
第一行是测试数据的数目M（1<=M<=10）。以下每行均包含一个整数n（1<=n<=10）。
输出：
输出每组测试数据有多少种分法。
分析：
对于整数划分，相当于把正整数n写成下面形式：
n=n1+n2+…+nk （其中n≥n1≥n2≥…≥nk≥1，k≥1），则{n1, n2, ……,nk}为n的一个划分。
现假设n1 <= m，即：{n1, n2, ……,nk}中最大的数不超过m，则称{n1, n2, ……,nk}是n的一个m上限划分。记n的m上限划分为f(n,m)。因此，此题的解便是f(n,n)。对于f(n,m)，分析可得下面的递推关系式：
1、当n = 1时，f(n,m)=1。即1只有{1}这一种划分。
2、当m = 1时，f(n,m)=1。即此时只有{1, 1,……,1}（共n个1）这一种划分。
3、当m = n时，f(n,m) = f(n,n) = f(n, n-1) + 1。其中"+1"对应的就是{n}这种划分，其他的划分中，必定所有数都小于n。
4、当m > n时， f(n,m) = f(n,n)，因为n的划分中不可能存在大于n的数。
5、当m < n时， f(n,m) = f(n-m, m) + f(n, m-1)。其中f(n-m,m)表示包含m的划分，f(n,m-1)表示不包含m的划分。
代码：
根据上面的递推式，同样可以写出递归和递推的代码。
递归代码仍然存在重复计算，时间代价大。
递推代码就是计算f(1,1)到f(n,n)的过程，所以时间和空间复杂度都是O(n^2)，而且由于f(n,m)是和f(n-m,m)、f(n,m-1)，所以不太适合进行空间复杂度的优化。
1 #include <stdio.h> 2 #include <string.h> 3 int fun(int n, int m) 4 { 5 if(n == 1 || m == 1) return 1; 6 else if(n < m) return fun(n, n); 7 else if(n == m) return (1 + fun(n, m - 1)); 8 else return (fun(n, m - 1) + fun(n - m, m)); 9 } 10 int main(){ 11 int n; 12 while(~scanf("%d", &n)) 13 { 14 printf("%d\n", fun(n, n)); 15 } 16 return 0; 17 }//超时
//超时改进，在计算的过程中记录一些已经算过的值，避免重复的计算
#include <stdio.h> #include <string.h> int dp[105][105];//把计算过的fun(n,m)存下来 bool flag[105][105]; int fun(int n, int m) { if(flag[n][m]==1) return dp[n][m]; if(n == 1 || m == 1) return 1; else if(n < m) { int tmp=fun(n,n); dp[n][n]=tmp; flag[n][n]=1; return tmp; } else if(n == m) { int tmp=1 + fun(n, m - 1); dp[n][m]=tmp; flag[n][m]=1; return tmp; } else{ int tmp1=fun(n,m-1); int tmp2=fun(n-m,m); int tmp=tmp1+tmp2; dp[n][m-1]=tmp1; flag[n][m-1]=1; dp[n-m][m]=tmp2; flag[n-m][m]=1; dp[n][m]=tmp; flag[n][m]=1; return tmp; } } int main(){ int n; int i,j; for(i=1;i<=100;i++){ for(j=1;j<=100;j++){ flag[i][j]=0; if(i==1) { dp[i][j]=1; flag[i][j]=1; } else if(j==1) { dp[i][j]=1; flag[i][j]=1; } } } for(i=1;i<=100;i++){ dp[i][i]=fun(i,i); flag[i][i]=1; } while(scanf("%d", &n)!=EOF) { printf("%d\n", fun(n,n)); } return 0; }
原文：http://www.cnblogs.com/yexinyu/p/6529763.html