描述

整数划分问题是算法中的一个经典命题之一。把一个正整数n表示成一系列正整数之和：

正整数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

输入输出样例

注意本题是求值问题，而非求最优解问题，不需要逐个输出各种情况，仅需输出最优值即可

算法分析

对于f(6,4)来说


初始值也就是我们要求的正整数n的划分数p(n)=f(n,n)

代码

#include<iostream>
using namespace std;
int split(int n,int m)
{if(n==1||m==1)return 1;else if (n<m)return split(n,n);else if(n==m)return split(n,n-1)+1;elsereturn split(n,m-1)+split(n-m,m);
}int main()
{int n;cin>>n;cout<<split(n,n);
}