斐波那契数

一、斐波那契数

1.1、暴力破解

class Solution:
    def fib(self, N: int) -> int:
        if N == 0:
            return 0
        elif N == 1:
            return 1
        else:
            return self.fib(N - 1) + self.fib(N - 2)

n = 20的递归树 这个递归树怎么理解？就是说想要计算原问题 f(20)，我就得先计算出子问题 f(19) 和 f(18)，然后要计算 f(19)，我就要先算出子问题 f(18) 和 f(17)，以此类推。最后遇到 f(1) 或者 f(2) 的时候，结果已知，就能直接返回结果，递归树不再向下生长了。

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

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

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

所以，这个算法的时间复杂度为 O(2n)，指数级别爆炸。

观察递归树，很明显发现了算法低效的原因：存在大量重复计算，比如 f(18) 被计算了两次，而且你可以看到，以 f(18) 为根的这个递归树体量巨大，多算一遍，会耗费巨大的时间。更何况，还不止 f(18) 这一个节点被重复计算，所以这个算法及其低效。

这就是动态规划问题的第一个性质：重叠子问题。下面，我们想办法解决这个问题。

1.2、带备忘录的递归解法

class Solution:
    def fib(self, N: int) -> int:
        if N == 0:
            return 0
        dictFib = {}
        
        return self.helper(dictFib, N)
    # 带备忘录的递归解法
    def helper(self, dictFib: {}, n: int) -> int:
        if n == 1 or n == 2:
            return 1
        if n in dictFib:
            return dictFib[n]
        # 每次计算完了，不急于返回，现将计算的结果存入备忘录中
        dictFib[n] = self.helper(dictFib, n - 1) + self.helper(dictFib, n - 2)
        return dictFib[n]

现在，画出递归树，你就知道「备忘录」到底做了什么。 实际上，带备忘录的递归算法，把一棵存在巨量冗余的递归树通过剪枝，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。

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

子问题个数，即图中节点的总数，由于本算法不存在冗余计算，子问题就是 f(1), f(2), f(3) … f(20)，数量和输入规模n=20 成正比，所以子问题个数为O(n)。

解决一个子问题的时间，同上，没有什么循环，时间为 O(1)。

所以，本算法的时间复杂度是 O(n)。比起暴力算法，是降维打击。

至此，带备忘录的递归解法的效率已经和动态规划一样了。实际上，这种解法和动态规划的思想已经差不多了，只不过这种方法叫做自顶向下，动态规划叫做自底向上。

自顶向下：注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从一个规模较大的原问题比如说f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 触底，然后逐层返回答案，这就叫自顶向下。

自底向上： 反过来，我们直接从最底下，最简单问题规模最小的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(20)，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。

1.3、动态规划

class Solution:
    # 动态规划
    def fib(self, N: int) -> int:
        if N == 0:
            return 0
        dictFib = {}
        dictFib[1] = 1
        dictFib[2] = 1
        # 自底向顶, 
        for i in range(3, N+1): # 注意此处N+1
            dictFib[i] = dictFib[i - 1] + dictFib[i - 2]
        return dictFib[N]

画个图就很好理解了，而且你发现这个 DP table 特别像之前那个剪枝后的结果，只是反过来算而已。实际上，带备忘录的递归解法中的备忘录，最终完成后就是这个 DP table，所以说这两种解法其实是差不多的，大部分情况下，效率也基本相同。

这里，引出动态转移方程这个名词，

1.4、动态转移方程

实际上就是描述问题结构的数学形式： 为啥叫状态转移方程？为了听起来高端。你把 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)：

class Solution:
    # 动态转移方程
    def fib(self, N: int) -> int:
        if N