509. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

• 0 <= n <= 30

动态规划-暴力递归

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

递归算法的时间复杂度怎么计算？就是用子问题个数乘以解决一个子问题需要的时间。

首先计算子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 O(2^n)。

然后计算解决一个子问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) 一个加法操作，时间为 O(1)。

所以，这个算法的时间复杂度为二者相乘，即 $O(2^n)$，指数级别，爆炸。

算法低效的原因：存在大量重复计算，比如计算 f(n) 时需要计算 f(n-2)，计算 f(n-1) 时也需要计算 f(n-2)。

动态规划，备忘录优化

int fib(int N) {
    // 备忘录全初始化为 0。因为要计算memo[n]，所以要N+1个位置。
    int[] memo = new int[N + 1];
    // 进行带备忘录的递归
    return helper(memo, N);
}

int helper(int[] memo, int n) {
    // base case
    if (n == 0 || n == 1) return n;
    // 已经计算过，不用再计算了
    if (memo[n] != 0) return memo[n];
    
    memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
    return memo[n];
}

本解法不存在冗余计算，子问题就是 f(1), f(2), f(3) … f(n)，数量和输入规模 n 成正比，所以子问题个数为 O(n)。

所以，本解法的时间复杂度是 O(n)。

动态规划-数组递推

int fib(int N) {
    if (N == 0) return 0;
    int[] dp = new int[N + 1];
    
    // base case
    dp[0] = 0; dp[1] = 1;
    
    // 状态转移
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[N];
}

动态规划-数组递推-滚动更新

class Solution {
    public int fib(int n) {
        if (n == 0 || n == 1) {
            // base case
            return n;
        }
        
        // 分别代表 dp[i - 1] 和 dp[i - 2]
        int dp_i_1 = 1, dp_i_2 = 0;
        for (int i = 2; i <= n; i++) {
            // dp[i] = dp[i - 1] + dp[i - 2];
            int dp_i = dp_i_1 + dp_i_2;
            // 滚动更新，记录本轮的数，下轮要用到
            dp_i_2 = dp_i_1;
            dp_i_1 = dp_i;
        }
        
        // 这里不能返回dp_i，因为dp_i是在for循环里定义的，外面访问不到，它就相当于一个临时变量。
        // 最终dp_i的值被赋给了dp_i_1，所以dp_i就没用了
        return dp_i_1;
    }
}

通项公式-涉及到开方，需要用double，然后转成int

斐波那契数 $F(n)$ 是齐次线性递推，根据递推方程 $F(n)=F(n-1)+F(n-2)$ ，可以写出这样的特征方程:

$$x^2=x+1$$

求得 $x_1=\frac{1+\sqrt{5}}{2}$， $x_2=\frac{1-\sqrt{5}}{2}$ 。设通解为 $F(n)=c_1 x_1^n+c_2 x_2^n$ ，代入初始条件 $F(0)=0$，$F(1)=1$，得 $c_1=\frac{1}{\sqrt{5}}$，$c_2=-\frac{1}{\sqrt{5}}$ 。因此斐波那契数的通项公式如下:

$$F(n)=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$$

得到通项公式之后，就可以通过公式直接求解第 $n$ 项。

class Solution {
    public int fib(int n) {
        double sqrt5 = Math.sqrt(5);
        double fibN = Math.pow((1 + sqrt5) / 2, n) - Math.pow((1 - sqrt5) / 2, n);
        return (int) Math.round(fibN / sqrt5);
    }
}

代码中使用的 pow 函数的时空复杂度与 CPU 支持的指令集相关，这里不深入分析。