/*
问题描述 一个正整数可以划分为多个正整数的和，比如n=3时： 3；1＋2；1＋1＋1； 共有三种划分方法。 给出一个正整数，问有多少种划分方法。 输入格式 一个正整数n 输出格式 一个正整数，表示划分方案数 样例输入 3 样例输出 3 数据规模和约定 n<=100
思路： 相当与 有m个环 放在 k 个 柱子上（想象汉诺塔）， 注意：因为与顺序无关 所以 我们假设左边柱子上的环不大于右边柱子上的环 （即 按从大到小的排列顺序 例如 5=1 4 5= 2 3 而不是 5=4 1 或5=3 2）
例如 有 5个球环 1个 柱子 （m=5,k=1）如下图 只有一种情况
那摩要是5个环 有2个柱子 （m=5,k=2）这又该怎么放，只有一步一步来。 1.假设第一根柱子 放一个环 那摩 第二根柱子只有把剩下4个放完，这是一种情况 （5=1 4）
2.假设我将两个柱子都放一个如下图 就相当于,柱子上没放东西 即 将m=5，k=2降为m=3,k=2
然后就假设先放一个 ，剩下的就只能全放另一个了
以此类推 。。。。
*/
DFS 实现:
代码语言：javascript复制#include<stdio.h>
long long int vis[101][101]={0};//用于 优化 记录 剪枝
long long int f(int m,int k)
{ if(vis[m][k]!=0)return vis[m][k];//当前 要把 m 拆分 k 部分 有多少种情况
if(k==1||k==m)return 1;//当k==1 剩下的就是最后一个数 k==m 此情况 直接全部放 1；
if(m<k)return 0;//保证按顺序执行
return vis[m][k]=f(m-1,k-1) f(m-k,k);//当前位放一个 或者所有位都放一个（相当于没放）
}
int main()
{
int n,i;long long int sum=0;
scanf("%d",&n);
for(i=1;i<=n;i )
sum =f(n,i); //把 m 拆分成 i位；
printf("%lld",sum);
return 0;
} DP实现：
代码语言：javascript复制#include<stdio.h>
int main(){
int n,k; long long int f[105][105]={0};//f[n][k] 代表n划分k位的方案数
scanf("%d",&n);
for(int i=1;i<=n;i )f[i][1]=1;//所有k=1 都是
f[0][0]=1;
for(int i=1;i<=n;i ){
for(int j=1;j<=n&&j<=i;j )f[i][j]=f[i-1][j-1] f[i-j][j];
}
long long int sum=0;
for(int i=1;i<=n;i ) sum =f[n][i];
printf("%lldn",sum);
return 0;
}
