1:问题描述：
整数划分问题是将正整数n表示成一系列正整数之和：n=n1+n2+n3+...+nk，其中n1>=n2>=n3>=...nk>=1,这种表示方法称为整数划分。求正整数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+1
问题分析：
为正整数n划分数，为了容易找到递归关系，考虑增加一个自变量，其中n为给定的正整数，m为划分中的最大加数，划分个数记为f(n,m)这样就可以找出如下递归关系：
一：最大加数m<=1的时候，这时候任何正整数都只有一种划分方法，即：n=1+1+1+...1;
二：最大加数m>n的时候（实际上m不能大于n）这个时候 f(n,m)=f(n,n);
三：最大加数m=n的时候，这时，分为两种情况：
1：包括n,这时正整数与最大加数一样，划分方法只有一种,{n}；
2：若不包括n ，这个时候最大加数为n-1，所以划分方法为 :f(n,n-1);
所以，当m=n时，f(n,m)=f(n,n-1)+1;
四：最大加数m<n,这个时候同样分为两种情况：
1：包括m ,这个时候最大加数就是m,划分方法为:f(n-m,m);
2：不包括m ，这个时候最大加数就是m-1,划分方法为:f(n,m-1);
所以，当m<n时，f(n,m)=f(n,m-1)+f(n-m,m)
编码如下
递归：
#include<iostream> using namespace std; int f(int n, int m) { if(m<1||n<1) { return 0; } else if (m>n){ return f(n,n); } else if(m==n){ return (f(n,m-1)+1); } else{ return (f(n-m,m)+f(n,m-1)); } } int main() { int n; cin>>n; cout<<f(n,n)<<endl; return 0; }
递推：
#include<iostream> using namespace std; int main() { int i,j,m,n; int f[100][100]; cin>>n>>m; for(i=1;i<=m;i++){ f[0][i]=1; } for(i=1;i<=n;i++){ f[i][0]=0; } for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ if(i<j){ f[i][j]=f[i][i]; }else if(i==j){ f[i][j]=(f[i][j-1]+1); } else{ f[i][j]=(f[i][j-1]+f[i-j][j]); } } } cout<<f[n][m]<<endl; }
