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;
}
