蓝桥杯算法提高VIP-数的划分 （C++代码） 递归求解！！转化为往盒子里放球的数学模型

解题思路:  数学模型：看成 有n个球要放到k个盒子里，变化的是(盒子)k的数目。   1。如果盒子数为1或者n，都只有1种方法    2.如果球数小于盒子数，必定有n-k个盒子为0，去掉这些盒子也没影响，即fun(n,n) 所以可直接返回0     3.最重要的地方！！   如果球数大于盒子数    分为两种情况！    第一：所有盒子都放了球，则可以相当于把所有盒子都取出一个球，方案数不变  即为fun(n-k,k)    第二:至少有一个盒子为空格  fun(n-1,k-1)

注意事项:

参考代码:

#include<iostream>
using namespace std;
int count=0,n;
const int N=105;
long long book[N][N];//用于标记 
 long long fun(int m,int k){
     if(book[m][k]!=0)  return book[m][k]; //如果是已经标记过的情况，直接返回 
     if(m<k) return 0;  
       if(k==1||m==k)  return 1;//k=1即分一组，就只有n。 m==k表示每个组为1 
      return book[m][k]=fun(m-k,k)+fun(m-1,k-1);
 }             //两种情况 
int main(){
   cin>>n;
    int i;
    for(i=1;i<=n;i++)
      count+=fun(n,i);
     cout<<count;
  return 0;}