题目描述

写一个函数，输入 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。To do it!
示例1 输入： n = 2，输出： 1
示例2 输入： n = 5，输出： 5
提示： 0 <= n <= 100

题解

记忆递归

采用暴力递归的方式包含了大量重复的递归计算，例如 f(n - 1) 和 f(n - 2) 两者向下递归需要各自计算 f(n - 2)，总时间复杂度为 O( $2^n$ )，时间超限。我们可以新建一个长度为 n + 1 的数组，用于递归时存储 f(0) 到 f(n) 的值，重复遇到某个数字就直接从数组中取用，避免了重复的递归计算。

// 单纯递归会重复计算相同值很多次
// 可以利用 hashmap 存储 n 和 f(n) 的映射
class Solution {
    unordered_map<int, int> f;  // n, f(n)
    const int mod = 1000000007;
public:
    int fib(int n) {
        if (n < 2) return n;
        if (f.find(n) != f.end()) return f[n];
        f[n] = (fib(n - 1) + fib(n - 2)) % mod;
        return f[n];
    }
};

// 也可以直接使用 vector<int>(n + 1);
class Solution {
private:
    const int mod = 1000000007;
    vector<int> arr;
    int f(int n) {
        if (n < 2) return n;
        if (arr[n] != -1) return arr[n];
        arr[n] = (f(n - 1) + f(n - 2)) % MOD;
        return arr[n];
    }
public:
    int fib(int n) {
        arr = vector<int>(n + 1, -1);
        return f(n);
    }
};

每个数值只计算一次，再遇到就不往下计算了，所以节点数即递归次数，为 2n - 1 次。

每次递归时间和空间复杂度均为 O(1)，递归次数为 O(2n - 1) = O(n)。还有额外空间为 O(n) 的数组。
时间复杂度：O(n)，空间复杂度：O(n)

动态规划

递归是自上而下的求解过程，我们可以自下而上，求 f(0), f(1), f(2) = f(1) + f(0), f(3) = f(2) + (1)，此时 f(0) 的值已经用不到了，利用 f(n) = f(n - 1) + f(n - 2)，每次计算只需要存储三个值。
假设有变量 a, b, c:

a = f(0), b = f(1), c = a + b = f(2)
a = b = f(1), b = c = f(2), c = a + b = f(3)
a = b = f(2), b = c = f(3), c = a + b = f(4)
…

斐波那契数存在递归关系，即可用动态规划求解。动态规划的转移方程即为递推关系方程，边界条件就是 f(0), f(1)。本应该利用长度为 n 的数组以循环实现，但是我们只需要存储三个值，便可把空间复杂度优化为 O(1)。算法详解

class Solution {
private:
    const int MOD = 1000000007;
public:
    int fib(int n) {
        if (n <= 1) return n;
        int a = 0, b = 1, c = a + b;
        // 此时 c = f(2)，循环从 c = f(3) 算到 c = f(n)
        for (int i = 3; i <= n; i++) {
            a = b;
            b = c;
            c = (a + b) % MOD; // 题目要求取模计算，避免超出整数范围
        }
        return c;
    }
};

时间复杂度：O(n)，空间复杂度：O(1)

矩阵快速幂

使用矩阵快速幂的方法可以降低时间复杂度。首先我们构建这样一个递推关系：

$\begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}F(n)\\F(n-1)\end{bmatrix}\;=\;\begin{bmatrix}F(n)\;+\;F(n-1)\\F(n)\end{bmatrix}\;=\;\begin{bmatrix}F(n+1)\\F(n)\end{bmatrix}$

于是：

$\begin{bmatrix}F(n+1)\\F(n)\end{bmatrix}\;=\;\;\begin{bmatrix}1&1\\1&0\end{bmatrix}^n\begin{bmatrix}F(1)\\F(0)\end{bmatrix}$

令：

$M\;=\;\begin{bmatrix}1&1\\1&0\end{bmatrix}$

所以我们只需快速计算矩阵 M 的 n 次幂，就可以得到 F(n) 的值。如果直接求取 $M^n$ ，时间复杂度是 O(n)，可以定义矩阵乘法，然后用快速幂算法来加速这里 $M^n$ 的求取。快速幂 & 矩阵快速幂笔记

class Solution {
    const int mod = 1000000007;
    vector<vector<long>> multiply(vector<vector<long>>& a, vector<vector<long>>& b) {
        vector<vector<long>> ret(2, vector<long>(2, 0));       // 假设已知均为 2*2 矩阵
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < 2; ++k) {
                    ret[i][j] += a[i][k] * b[k][j];
                }
                ret[i][j] %= mod;
            }
        }
        return ret;
    }
    vector<vector<long>> pow(vector<vector<long>>& M, int n) {
        vector<vector<long>> ret = {{1, 0}, {0, 1}};    // 单位矩阵 I
        while (n > 0) {
            if (n & 1) ret = multiply(ret, M);
            n >>= 1;
            M = multiply(M, M);
        }
        return ret;
    }
public:
    int fib(int n) {
        if (n < 2) return n;
        vector<vector<long>> M = {{1, 1}, {1, 0}};
        return pow(M, n - 1)[0][0];
    }
};