【萌新解题】斐波那契数列

看到题目的第一眼，我相信大部分人跟我一样，都可以闭着眼睛通过递归写出如下代码：

class Solution {
    public int fib(int N) {
        if (N < 2) {
            return N;
        }
        return fib(N-1) + fib(N-2);
    }
}

递归的好处就是代码简单，也符合计算机的思维，代码提交后，可以看到结果如下：

image.png

可以看到，由于是递归，而且这个递归函数中存在大量重复计算，耗时较长；递归算法的时间复杂度就是用子问题个数乘以解决一个子问题所需的时间，斐波那契数列这个递归可以想象成一棵二叉树，二叉树的节点对应一个递归函数（例如 fib(4)），子问题个数的时间复杂度为 O(2ᴺ)，而解决一个子问题所需时间是一次加法时间，例如 fib(1) + fib(2) 的时间，也就是 O(1)，因此上面这个递归解法的时间复杂度是 O(2ᴺ)。

一种优化方法是通过备忘录把计算的结果保存下来，避免重复计算，例如通过数组或者哈希表都可以，如下所示，我们使用数组作为备忘录的实现：

class Solution {
    public int fib(int N) {
        if (N == 0) {
            return 0;
        }
        // 初始化备忘录数组，数组大小是 N+1，因为数组是从0开始，而题目要求的是fib(N)的值
        int[] memo = new int[N+1];
        return helper(memo, N);
    }
 
    /**
     * 辅助函数
     */
    private int helper(int[] memo, int N) {
        // base case
        if (N == 1 || N == 2) {
            return 1;
        }
 
        // 备忘录模式，避免重复计算
        if (memo[N] != 0) {
            return memo[N];
        }
 
        // 递归调用，并保存返回值到备忘录数组中
        memo[N] = helper(memo, N-1) + helper(memo, N-2);
 
        return memo[N];
    }
}

通过引入备忘录，我们避免了大量的重复计算，子问题个数为 O(N)，解决一个子问题的时间还是 O(1)，因此上面这个增加了备忘录的递归解法的时间复杂度是 O(N)，代码执行结果如下：

image.png

可以看到，执行耗时得到大幅下降，而因为使用了额外的空间 memo 数组，因此，内存消耗增加了，这是典型的空间换时间。

好了，到这里其实这个问题的最优解也得到了，因为时间复杂度已经是 O(N) 了，不可能再进一步降低。但如果你之前有了解过动态规划的话，因为知道，斐波那契数列问题也可以使用动态规划思想来解决。动态规划问题的一般形式是求最值，例如求最长递增子序列，最小编辑距离等，而斐波那契数列问题本身其实没有求最值，但因为可以用来很好的演示动态规划思想和解题套路，因此喜提动态规划第一题的称号。

在正式介绍动态规划的解题套路之前，我们先来对比下斐波那契数列问题使用递归和动态规划的区别：

• 递归解法是自顶向下的思想，例如，我们是从一个规模较大的原问题，例如 fib(10) 开始，一步一步向下分解规模（如分解成 fib(9) 和 fib(8) 两个子问题），然后逐层返回答案，最终得到原问题

• 动态规划解法是自底向上的思想，例如，我们是从规模最小的问题开始，例如 fib(1)、fib(2) 开始往上推导，直到得到 fib(10)，因此，动态规划问题一般都使用循环迭代来代替递归来完成计算。

参考代码随想录，本文我们使用的动态规划解题六步骤如下：

1. 确定 dp 数组以及下标的含义（dp数组可能是一维数组、二维数组等）

2. 确定递推公式

3. dp 数组如何初始化

4. 确定 dp 数组的遍历顺序，可能是正向遍历、反向遍历、斜向遍历等

5. 举例推导dp数组，通过把dp数组打印出来，并和自己人脑计算的结果对比，用于调试使用

6. 思考是否可以状态压缩，进一步提升空间效率

好，把上面的解题步骤套用到斐波那契数列问题，得到结果如下：

1. 确定 dp 数组以及下标的含义：dp[i] 的含义是斐波那契数列中第 i 个数的取值

2. 确定递推公式：题目中已经给出来了，即 dp[n] = dp[n-1] + dp[n-2]

3. dp 数组如何初始化：题目中已经给出来了，即 dp[0]=0; dp[1]=1;

4. 确定 dp 数组的遍历顺序：当想得到 dp[n] 的值时，我们首先得知道 dp[n-1] 和 dp[n-2] 的值，因此，我们需要从小到大遍历数组

5. 举例推导dp数组：需要调试时使用即可

6. 思考是否可以状态压缩：如果现在想不清楚，可以等我们写完上面代码后可以再考虑

最终得到的动态规划解法代码如下：

class Solution {
    public int fib(int N) {
        if (N == 0) {
            return 0;
        }
 
        // 定义dp数组
        int[] dp = new int[N+1];
 
        // 确定dp数组的初始化状态
        dp[0] = 0;
        dp[1] = 1;
 
        // 循环迭代，dp数组遍历顺序是从小到大
        for (int i=2; i<=N; ++i) {
            dp[i] = dp[i-1] + dp[i-2];
            
            // 打印dp数组，此处略
        }
 
        return dp[N];
    }
}

执行结果如下：

image.png

时间复杂度和空格复杂度都是 O(N)，最后，我们再来考虑下状态压缩，状态压缩指的是缩小 dp 数组的大小，只存储必要的数据，这样可以进一步减少空间复杂度，在本题中，我们可以看到 dp[n] = dp[n-1] + dp[n-2]，也就是想得到 dp[n]，只需要存储 dp[n-1] 和 dp[n-2] 这两个状态即可，也就是可以把 dp 数组的长度从 N+1 缩小为 2，这样的话我们其实也不需要使用数组了，直接使用两个变量即可，改造后的代码如下所示：

class Solution {
    public int fib(int N) {
        if (N == 0) {
            return 0;
        }
 
        // 确定dp数组的初始化状态
        int prev = 0;
        int current = 1;
 
        int sum = 0;
        // 循环迭代，dp数组遍历顺序是从小到大
        for (int i=2; i<=N; ++i) {
            sum = prev + current;
            prev = current;
            current = sum;
        }
 
        return current;
    }
}