题目地址(509. 斐波那契数)

https://leetcode-cn.com/problems/fibonacci-number/

题目描述

  1. 斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
  3. F(0) = 0，F(1) = 1
  4. F(n) = F(n - 1) + F(n - 2)，其中 n > 1
  7. 给你 n ，请计算 F(n) 。
  11. 示例 1：
  13. 输入：2
  14. 输出：1
  15. 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
  18. 示例 2：
  20. 输入：3
  21. 输出：2
  22. 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
  25. 示例 3：
  27. 输入：4
  28. 输出：3
  29. 解释：F(4) = F(3) + F(2) = 2 + 1 = 3
  34. 提示：
  36. 0 <= n <= 30

前置知识


公司

  • 暂无

思路

常规的递归方式十分的低效 但是十分低效，低效在哪里？假设 n = 20，画出递归树是下面的样子
image.png
就是说想要计算原问题 f(20)，我就得先计算出子问题 f(19) 和 f(18)，然后要计算 f(19)，我就要先算出子问题 f(18) 和 f(17)，以此类推。最后遇到 f(1) 或者 f(2) 的时候，结果已知，就能直接返回结果，递归树不再向下生长了。
递归算法的时间复杂度怎么计算？就是用子问题个数乘以解决一个子问题需要的时间。
首先计算子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 O(2^n)。
然后计算解决一个子问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) 一个加法操作，时间为 O(1)。
所以，这个算法的时间复杂度为二者相乘，即 O(2^n)，指数级别，爆炸。
观察递归树，很明显发现了算法低效的原因：存在大量重复计算，比如 f(18) 被计算了两次，而且你可以看到，以 f(18) 为根的这个递归树体量巨大，多算一遍，会耗费巨大的时间。更何况，还不止 f(18) 这一个节点被重复计算，所以这个算法及其低效。
这就是动态规划问题的第一个性质：重叠子问题。下面，我们想办法解决这个问题。
明确了问题，其实就已经把问题解决了一半。即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。
一般使用一个数组充当这个「备忘录」，当然你也可以使用哈希表（字典），思想都是一样的。
现在，画出递归树，你就知道「备忘录」到底做了什么
image.png
实际上，带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。
image.png
递归算法的时间复杂度怎么计算？就是用子问题个数乘以解决一个子问题需要的时间。
子问题个数，即图中节点的总数，由于本算法不存在冗余计算，子问题就是 f(1), f(2), f(3) … f(20)，数量和输入规模 n = 20 成正比，所以子问题个数为 O(n)。
解决一个子问题的时间，同上，没有什么循环，时间为 O(1)。
所以，本算法的时间复杂度是 O(n)。比起暴力算法，是降维打击。
至此，带备忘录的递归解法的效率已经和迭代的动态规划解法一样了。实际上，这种解法和迭代的动态规划已经差不多了，只不过这种方法叫做「自顶向下」，动态规划叫做「自底向上」。
啥叫「自顶向下」？注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 这两个 base case，然后逐层返回答案，这就叫「自顶向下」。
啥叫「自底向上」？反过来，我们直接从最底下，最简单，问题规模最小的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(20)，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。
啥叫「状态转移方程」？其实就是为了听起来高端。你把 f(n) 想做一个状态 n，这个状态 n 是由状态 n - 1 和状态 n - 2 相加转移而来，这就叫状态转移，仅此而已。
你会发现，上面的几种解法中的所有操作，例如 return f(n - 1) + f(n - 2)，dp[i] = dp[i - 1] + dp[i - 2]，以及对备忘录或 DP table 的初始化操作，都是围绕这个方程式的不同表现形式。可见列出「状态转移方程」的重要性，它是解决问题的核心。而且很容易发现，其实状态转移方程直接代表着暴力解法。
千万不要看不起暴力解，动态规划问题最困难的就是写出这个暴力解，即状态转移方程。只要写出暴力解，优化方法无非是用备忘录或者 DP table，再无奥妙可言。
这个例子的最后，讲一个细节优化。细心的读者会发现，根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)：
这个技巧就是所谓的「状态压缩」，如果我们发现每次状态转移只需要 DP table 中的一部分，那么可以尝试用状态压缩来缩小 DP table 的大小，只记录必要的数据，上述例子就相当于把DP table 的大小从 n 缩小到 2。后续的动态规划章节中我们还会看到这样的例子，一般来说是把一个二维的 DP table 压缩成一维，即把空间复杂度从 O(n^2) 压缩到 O(n)。

关键点


代码

  • 语言支持：Java

Java Code:

递归方式:

时间复杂度为 509. 斐波那契数 3 - 图4

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

动态规划方式:

class Solution {
        public int fib(int n) {
            if (n == 0) {
                return 0;
            }
            //定义dp数组 也就是备忘录 将可能重复的数据都放到里面 下次用到的时候就不需要再计算一遍
            //斐波那契数列本身使用递归的方式 会计算很多的重复数据 这样的话每个数据可能会被计算不止一遍 时间复杂度上是指数级的 2^n
            //使用了动态规划的方式 每个数据只会被计算一边 然后就保存到动态的数组中 这时候时间复杂度就优化到了 n 常数级
            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];
        }
    }

优化了空间复杂度

int fib(int n) {
    if (n < 1) return 0;
    if (n == 2 || n == 1) 
        return 1;
    int prev = 1, curr = 1;
    for (int i = 3; i <= n; i++) {
        int sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}

复杂度分析

令 n 为数组长度。

  • 时间复杂度：509. 斐波那契数 3 - 图5#card=math&code=O%28n%29&id=SA6XK)
  • 空间复杂度：509. 斐波那契数 3 - 图6#card=math&code=O%28n%29&id=HJ2Sr)