前言斐波那契数列是一个非常经典的问题。虽然很简单，但是在优化它优化算法的时候可以推广到很多实际问题。它的概念很简单，我们来看看LeetCode真题中对它的定义：斐波那契数列，通常用F(n)表示，组成一个数列，称为斐波那契数列。该序列以0和1开头，后面的每个数字都是前两个数字的总和。即：F(0)=0，F(1)=1F(N)=F(N-1)+F(N-2)，其中N>1。给定N，计算F(N)。首先，让我们预览一下斐波那契数列的样子：1、1、2、3、5、8、13、21、34青铜时代-递归求解。在本文中，下面出现的fib(n)表示n的解。有了定义之后，我们对于这个问题的第一反应就是可以用“递归”来解决。这个想法也很简单。我们只需要定义初始状态，即fib(1)=1，fib(2)=1，那么假设需要fib(3)，只需要fib(2)+fib(1)，并且很快。在大约fib(50)时，它在我的笔记本电脑上运行了123.167秒，之后我什至无法想象。由于大量的递归调用加上不断的重新计算，该算法速度慢得令人无法接受。SilverAge-MemoSolutionBronzesolution有很多重复计算，例如fib(3)会计算fib(2)+fib(1)，而fib(2)会计算fib(1)+fib(0)。这个fib(1)是一个完全重复的计算。不应该为它再次递归调用，而应该在第一次解决后“记住”。解放地图中已经获得的，下次直接拿走，不用重复结算。这里使用iife函数形成闭包，保留私有变量memo。这是一个小技巧。此时fib(50)的计算速度已经达到了0.096秒，在50这个小数量级的情况下比青铜方案快了1200倍。一些说算法没用的人认为这些差异会随着硬件的进步而被抹平，所以我期待着硬件提升1000倍的那一天。GoldenAge-Dynamicprogramming上面的备忘方案看似完美，其实不然。备忘方案虽然优化了无用的重复方案，但是在速度上已经达到了一个相对最优的水平。但是对于第一种方案，没有被记忆的值还是会进入递归调用逻辑。比如f(10000)，然后是f(9999)，f(9998)...f(0)，必须递归调用，而在递归的过程中，这些调用栈是不断堆叠的，当函数调用深入，栈已经达到了数万层。此时会报一个熟悉的错误：RangeError:Maximumcallstacksizeexceededatc:\codes\leetcode-javascript\dynamicprogramming\Fibonaccisequence-509.js:20:19atc:\codes\leetcode-javascript\dynamicprogramming\FibonacciSequence-509。js:32:14让我们回过头来考虑一下。在备忘录的思路下，我们的解决路径是“自上而下”的。如果我们反过来想，就变成了“底”的解呢？也就是说，对于fib(10000)，我们从fib(1)，fib(2)，fib(3)开始……fib(10000)，从最小值开始求解，并将每个解的值保存在“内存”中（可以是数组，下标只是用来对应n的解值），得到下面的值都是直接从内存中的值中得到的，这样当计算到10000时，自然就得到了我们要求解的值，直接从内存中取值即可[10000]并返回。那么这个方案其实只需要一个for循环，没有任何递归逻辑。其实这是“动态规划”比较经典的方案。那么这个算法强大吗？对于fib(10000)上面两个方案是无能为力，用了0.114秒得到结果。对于fib(100000)用了0.827秒。顺便说一句，在JavaScript中，这个数字将显示为我nfinity因为它超过了最大值。其实解决方法也很简单，使用BigInt数据类型即可。总结本文通过一个简单的斐波那契数列例子来领略动态规划算法的美妙之处和强大的能力。相信看完这篇文章你就能知道，算法不是用来炫技的，而是可以真正解决效率问题的。
