题解 | #吃糖果#

#include <iostream>
using namespace std;

int f(int n)
{
    int g;
    if (n==1)
    g=1;
    else 
    if (n==2)
    g=2;
    else
    g=f(n-1)+f(n-2);
    return g;
}

int main() {
    int a;
    int m;
    while (cin >> a ) { // 注意 while 处理多个 case
    m=f(a);
    cout<<m<<endl;
    }
    return 0;
}
// 64 位输出请用 printf(\"%lld\")

实际上题目有提示了，可以猜出来用斐波那契数列。

分析：从后往前推

设求吃糖果

第n天可以选择吃一个或者两个，那么相应的第n-1天的选择数为f(n-1)与f(n-2)，由此得到递推式f(n)=f(n-1)+f(n-2)。

题目中天数取值范围为0到20，不太大，因此可以直接用递归法就可以快速解决。