题目来源：小蓝本周建新编著的《组合趣题》第1章计数问例22。

题目描述：小兔有n根萝卜，它每天至少要吃一棵，则当萝卜吃完时，不同的吃萝卜的情形有多少种？（1<=n<=64）

测试用例：输入 12， 输出2048

解题思路：（解法1）我们假设小兔有n根萝卜时，不同的吃萝卜的情形有F(n)种。我们先想一下当n=3时，F(3)怎么求？有以下几种吃法如下，

1天吃了1根萝卜的情况下，问题变成了剩2根萝卜时，有多少种情形？这样就把问题分成3类，每一类都是一个子问题，可以用递归方法解决。根据加法原理，F(3)=F(2)+F(1)+F(0)。所以F(n)就可以分成n类，F(n)=F(n-1)+F(n-2)+……+F(0)。初始化条件F(0)=1, F(1)=1。

代码实现：

#includeusing namespace std;typedef unsigned long long ull;int main(){  ull n, a[69]={1,1};  cin>>n;  for(int i=2;i<=n;i++){    for(int j=0;j      a[i]+=a[j];    }  }  cout<  return 0;}

（解法2）筷子法，这个解法来自于书上，思路很好，记录下来。

将n棵萝卜一字排开，编号为1到n号，小兔吃萝卜从1号开始依次吃，若某天最后吃完的是第k棵萝卜，则在第k棵萝卜后放一根筷子(其中1<=k<=n-1)。实际上就是用筷子把萝卜分成若干摊，每天依次吃其中一摊。于是问题转换为在n-1个位置上放筷子（每个位置至多放一根筷子），有多少种放法？而每个位置，可以放筷子，也可以不放筷子，根据乘法原理知，不同的放筷子的方法有2^(n-1)种。