从斐波那契看动态规划

type

status

date

slug

summary

斐波那契数列

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

首先计算子问题个数，即递归树中节点的总数。这棵递归树的高度为，所以二叉树的节点总数为。

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

所以，这个算法的时间复杂度为二者相乘，即，指数级别，爆炸。

观察递归树，很明显发现了算法低效的原因：存在大量重复计算。

比如 f(3) 被计算了两次，而且你可以看到，以 f(3) 为根的这个递归树体量大，多算一遍，会耗费时间。更何况还不止 f(3) 这一个节点被重复计算，所以这个算法效率很差。这就是动态规划问题的第一个性质：重叠子问题。下面，我们想办法解决这个问题。

即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案后顺便记到「备忘录」里；每次遇到一个子问题别急着计算，先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。

对于斐波那契数列问题，我们需要一个备忘录记录子问题 f(x) 的值，其中 x 是一个非负整数，所以一般用一个一维数组 memo 充当备忘录就可以了，让 memo[x] 存储子问题 f(x) 的返回值。

当然，你也可以用一个哈希表来存储，思想都是一样的。

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

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

所以，本算法的时间复杂度是，比起指数级复杂度的暴力算法，已经非常高效了。

当遇到重复节点时，递归树不会向下生长，而是直接返回结果，这就是「剪枝」的效果

动态规划的解题方法了：无非就是先写出暴力解法，然后用「备忘录」剪枝消除重叠子问题嘛，动态规划就是这么简单。

第一种是带备忘录的递归解法，或称为「自顶向下」的解法，也就是我们上面展示的，一个递归函数带一个 memo 备忘录。

第二种是 DP table 的迭代解法，或称为「自底向上」的解法，用 for 循环去迭代 dp 数组进行求解。

这两者的本质是一样的，可以互相转化。迭代解法中的那个 dp 数组，就是递归解法中的 memo 数组。

为啥叫「自顶向下」？

比如刚才的递归解法，多次点击 if (n == 0 || n == 1) 可以看到递归树从上向下生长，从一个规模较大的原问题 f(5)，向下逐渐分解规模，直到 f(0) 和 f(1) 这两个 base case，然后逐层返回答案，这就叫「自顶向下」。

啥叫「自底向上」？就是反过来嘛。我们直接从最底下、最简单、问题规模最小、已知结果的 f(0) 和 f(1)（base case）开始往上推出 f(2), f(3)... 最后推出我们想要的 f(5)，这就是「自底向上」。

递归树从下向上传递结果的过程，就是 memo 数组从 base case 向右推算的过程，这就叫自底向上到这里你应该也观察出来了，其实整个计算过程就是在从左到右计算 memo 的值，那又何苦用递归了，搞这么复杂。一个 for 循环是不是就够用了？

有了上一步的启发，我们不再使用递归函数，直接创建一个数组（DP table），用一个 for 循环从 base case 开始从左到右进行计算即可。

这里，引出「状态转移方程」这个名词，实际上就是描述问题结构的数学形式：

为啥叫「状态转移方程」？其实就是为了听起来高端。

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，再无奥妙可言。

根据斐波那契数列的状态转移方程，当前状态 n 只和之前的 n-1, n-2 两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。

所以，可以进一步优化，把空间复杂度降为 O(1)O(1)。这也就是我们最常见的计算斐波那契数的算法：