题目内容：

输入一个整数$n$ ，求斐波那契数列的第$n$项。
假定从$0$开始，第$0$项为$0$。

数据范围

$0\leq n\leq 39$

样例

输入整数 n=5
返回 5

斐波那契数列想必大家都知道了吧！（不知道的点这）

它的做法也有很多很多种，这里就先写三种。

NO.1 递归

简洁明了但时间复杂度较高，不推荐使用。

class Solution {
public:
    int Fibonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
};

NO.2 记忆化搜索

把递归做法优化到了线性，不用再重复算同一项，但容易写错。

class Solution {
public:
    int f[40];

    int Fibonacci(int n) {
        if (n == 0)
            return 0;
        if (f[n])
            return f[n];
        if (n == 1 || n == 2)
            return 1;
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
};

NO.3 递推

这是我最推荐的一种做法，不容易写错且时间复杂度最低。

class Solution {
public:
    int Fibonacci(int n) {
        int f[40];
        f[0] = 0;
        f[1] = f[2] = 1;
        for (int i = 3; i <= n; i ++)
            f[i] = f[i - 1] + f[i - 2];
        return f[n];
    }
};

这篇题解到这里就结束了，祝各位看到的同学们$RP++$，我们……

下次再见！！！

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$