原文发表于公众号 “labuladong”，本文只是转载，略有改动，侵删。
暴力递归
斐波那契数列的数学形式就是递归的，如果写成代码就是：
int fib(int N) {
if (N == 1 || N == 2) return 1;
return fib(N - 1) + fib(N - 2);
}
代码简洁易懂，但是十分低效。低效在哪里？假设 n = 20，请画出递归树。
PS：但凡遇到需要递归的问题，最好都画出递归树，这样有利于分析算法的复杂度，寻找算法低效的原因。
这个递归树怎么理解？就是说如果我们要计算f(20)，就要先计算出子问题f(19)和f(18)，然后要计算f(19)，就要先算出子问题f(18)和f(17)，以此类推。最后遇到f(2)或者是f(1)时，结果已知，就可以直接返回结果，递归树不再向下生长。
递归算法的时间复杂度如何计算？子问题的个数乘以解决一个子问题需要的时间。
子问题的个数，即递归树中节点的数量。显然二叉树的节点总数为指数级别，所以子问题的个数为 2^n。
解决一个子问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) 一个加法操作，时间为O(1).
所以，这个算法的时间复杂度为 O(2^n)，指数级别。
观察递归树，很明显发现了算法低效的原因：存在大量重复计算，比如f(18)被计算了两次，而且，以f(18)为根的这个递归树体量巨大，多算一遍，会耗费巨大的时间，更何况不止f(18)一个节点被重复计算，所以这个算法极其低效。
这其实也是动态规划问题中的第一个性质：重复子问题。下面，我们想办法解决这个问题。
带备忘录的递归解法
既然耗时的原因是重复计算，那么我们可以制造一个“备忘录”，当然也可以使用哈希表（字典），思想都是一样的。
public function fib($n)
{
if ($n < 1) {
return 0;
}
$hash = [];
return self::helper($hash, $n);
}
public static function helper(array &$hash, $n)
{
if($n == 1 || $n == 2) {
// base case
return 1;
}
if(isset($hash[$n]) && $hash[$n]) {
return $hash[$n];
}
$hash[$n] = self::helper($hash, $n - 1) + self::helper($hash, $n - 2);
return $hash[$n];
}
现在，画出递归树，你就知道“备忘录”到底做了什么：
实际上，带“备忘录”的递归算法，把一颗存在巨量冗余的递归树通过“剪枝”，改造成了一幅不存在冗余的递归图，极大地减少了子问题（即递归图中节点）的个数。
递归算法的时间复杂度：子问题的个数乘以解决一个子问题需要的时间
子问题的个数为n，解决一个子问题没有循环，时间为O(1)。
所以，本算法的时间复杂度是O(n)。
至此，带备忘录的递归解法的效率已经和迭代的动态规划一样了。实际上，这种解法和迭代的动态规划思想已经差不多，只不过这种方法叫做“自顶向下”，动态规划叫做“自底向上”。
啥叫“自顶向下”？注意到我们刚才花的递归树，是从上向下延伸，都是从一个规模较大的问题比如
f(20)，向下逐渐分解规模，直到f(1)和f(2)触底，然后逐层返回答案，这就叫“自顶向下”。
啥叫“自底向上”？ 反过来，我们直接从最底下，最简单，问题规模最小的f(1)和f(2)开始往上推，知道推到我们想要的答案f(20)，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，改为由循环迭代来完成计算。
dp 数组的迭代解法
有了上一步“备忘录”的启发，我们可以把这个“备忘录”独立出来成为一张表，就叫做DP table 吧，在这张表上完成“自底向上”的推算。
public function fibDp($n)
{
$hash = [];
$hash[1] = $hash[2] = 1;
for ($i = 3; $i <= $n; $i ++) {
$hash[$i] = $hash[$i-1] + $hash[$i-2];
}
return $hash[$n];
}
这个问题结构的数据形式，就是：
一个细节优化，根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个DP table 来存储所有的状态，只需要想办法存储之前的两个状态即可。所以，算法可以进一步优化，把空间复杂度也将为O(1)。
public function fib($n)
{
if($n == 1 || $n == 2) {
return 1;
}
$pre = $cur = 1;
for ($i = 3; $i <= $n; $i ++) {
$sum = $cur + $pre;
$pre = $cur;
$cur = $sum;
}
return $cur;
}
ps:该文章转载于公众号labuladong，侵删。如果想了解学习关于算法的知识，请关注原作者 labuladong。
