这道题表面上是一道普普通通的递归，先放代码：

#include <cstdio>
using namespace std;
int f(int n)
{
    if(n <= 2)
        return 1;
    else
        return f(n - 1) + f(n - 2);
}
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d", f(n));
    return 0;
}

但是题目里写了n <= 45。直接这么写的话会TLE 传送TLE解法

所以，我们要用一个垃圾高大上的算法————记搜（记忆化搜索）

顾名思义，就是把东西记住，然后再去搜索（在这道题里是继续递归）。
这里，我们用一个数组F[50]来做记搜，只要F[n]没有东西，我们就在下一次递归的同时去给F[n]赋值为返回值。否则就返回F[n]。代码如下：

#include <cstdio>
using namespace std;
int F[50];
int f(int n)
{
    if(n <= 2)
        return 1;
    else if(F[n])
           return F[n];
    else
        return F[n] = f(n - 1) + f(n - 2);
}
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d", f(n));
    return 0;
}