1. 题目信息

1.1 题目描述

题目链接：剑指 Offer 10- I. 斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

1.2 测试用例

示例 1：

输入：n = 2
输出：1

示例 2：

输入：n = 5
输出：5

提示：

0 <= n <= 100

2. 题目分析

2.1 公式递推

直接用公式递推，注意计算过程中取模即可;

2.2 递归+备忘录

递归过程中，会导致很多重复计算，所以需要存个备忘录，避免重复计算！！！

直接开个足够大的数组吧，所以推荐方法1;

3. 代码详情

3.1 C++

3.1.1 公式递推

class Solution {
public:
    int fib(int n) {
        // 执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
        // 内存消耗：5.9 MB, 在所有 C++ 提交中击败了50.82%的用户
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int fn2 = 0; // f(n-2)
        int fn1 = 1; // f(n-1)
        int fn;
        const int mod = 1e9 + 7;
        for (int i = 2; i <= n; i++) {
            fn = (fn1 + fn2) % mod;
            fn2 = fn1;
            fn1 = fn;
        }
        return fn;
    }
};

3.1.2 递归+备忘录

class Solution {
    vector<int> memo_;
    const int mod_ = 1e9 + 7;
public:
    int fibRec(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n < memo_.size() && memo_[n]) {
            return memo_[n];
        }
        memo_[n] = (fibRec(n - 1) + fibRec(n - 2)) % mod_;
        return memo_[n];
    }
    int fib(int n) {
        memo_ = vector<int>(n+1);
        return fibRec(n);
    }
}

3.2 Python

递推计算

class Solution:
    def fib(self, n: int) -> int:
        # 执行用时：24 ms, 在所有 Python3 提交中击败了97.08%的用户
        # 内存消耗：15 MB, 在所有 Python3 提交中击败了35.43%的用户
        if (n == 0):
            return 0

        if (n == 1):
            return 1

        fn2 = 0 # // f(n-2)
        fn1 = 1 # // f(n-1)
        fn = 0
        mod = int(1e9 + 7)
        for i in range(2, n+1):
            fn = (fn1 + fn2) % mod
            fn2 = fn1
            fn1 = fn
        return fn