☮斐波那契数列与动态规划

一、斐波那契数列

斐波那契数列 又称兔子数列，它有这样的公式： Fn = Fn-1 + Fn-2。换句话说，下一个数字是前两个数字的和。

前两个数是1，然后是2（1+1），3（2+1），5(2+3)，8，13...

现在有一个需求是编写一个函数fib(n)返回第n个斐波那契数。

在编写函数之前，还想让大家了解一下动态规划的知识。

二、动态规划中的自顶向下和自底向上

图片来自书籍 算法导论 第15章动态规划。

三、两种思想在斐波那契数列数列问题种的体现

1. 自顶向下的思想（递归）

function fib(n){
    if (n <= 1) {
        return n
    }
    return fib(n - 1) + fib(n - 2)
}
// 三目简洁版
function fib(n) {
    return n <= 1 ? n : fib(n - 1) + fib(n - 2)
}
复制代码

很显然使用递归能完成需求，但是n较大时会变得很慢，调用该函数会挂起引擎一段时间，消耗所有CPU资源，测试结果可见下图，小伙伴们自己测试时千万不要将n设置的很大，否则你的该页面可能会崩溃的😅。

why? 为什么会这么慢？我们简单的画出递归树，就知道是为啥了👻

图片参考自现代JavaScript教程-递归和堆栈

我们可以清楚的看到 fib(3) 被计算了两次，fib(2) 被计算了三次。总计算量远远超过了 n，这造成仅仅对于计算 n=40 来讲，计算量就是巨量的。n越大，计算量就越大。

我们还可以选择不使用递归的解法👇🏿。

2. 自底向上的思想（循环）

function fib(n) { 
    let a = 1
    let b = 1
    for (let i = 3; i <= n; i++) { 
        let c = a + b
        a = b
        b = c
    } return b
}
// 可视化序列
a  b  c 
1, 1, 2
   a  b  c 
1, 1, 2, 3
      a  b  c 
1, 1, 2, 3, 5
         a  b  c 
1, 1, 2, 3, 5, 8
复制代码

该解法的思想就是动态规划种的自底向上，依次类推，直到我们得到需要的值，这比递归快得多，该解法的时间复杂度为O（n），而递归解法的时间复杂度为O(n^2)

四、总结

虽然递归有时解决问题很容易，但是还是要考虑算法的性能，是否出现过多重复的计算，如果出现过多重复的计算，那么这条路一定不是最正确的解法。

两种方法方法得到的算法具有相同的渐进运行时间，仅有的差异是在某些特殊情况下，自顶向下方法并未真正递归地考察所有可能的子问题。由于没有频繁的递归函数调用的开销，自顶向上的时间复杂性函数通常具有更小的系数。