蓝桥杯算法提高数的划分（图解DFS+DP）

问题描述
　　一个正整数可以划分为多个正整数的和，比如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 实现:

#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实现：

#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("%lld\n",sum);
    return 0;
}