蓝桥杯算法提高VIP-数的划分 （C语言代码）----------------C语言——菜鸟级

解题思路:深搜加剪枝

注意事项:

参考代码:

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