题目：

来源： 力扣（LeetCode）链接

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

分析

从题目我们就可以得出一个公式了，第n的等于第（n-1）的结果 加上 第（n-2）的结果

const fib = n => {
  const F = n => {
    return F(n-1) + F(n-2)
  }
  return F(n)
}

但是这样子F函数会无限递归下去，所以我们就要有一个退出条，题目也说了，就是n = 0 n = 1的时候有确定的结果，并且答案需要取模 1e9+7（1000000007），所以，改一下

const fib = n => {
  const F = n => {
    if(n === 1 || n === 0) {
      return n
    }
    let res = F(n-1) + F(n-2)
    return res % 1000000007
  }
  return F(n)
}

这样子，没问题，符合题意。

但是，提交的时候会发现超出时间限制
为什么？仔细看看
假如n = 100，F(100) = F(99) + F(98)

那么我就要算F(99) 和 F(98)的值:

F(99) = F(98) + F(97)
F(98) = F(97) + F(96)
F(97) = F(96) + F(95)
...
F(2) = F(1) + F(0) = 1 + 0 = 2

在这个过程中，我们可以发现是存在大量的重复计算的，每一个数字都会重复上一个数字的计算的过程，所以这个时长是非常耗时的，如下图的f(n-2) f(n-3) 等等：

F(n).png
既然是重复性的，那么我们就可以省略掉，采用缓存把结果记录下来，避免每次都重新计算，我之前写过一篇文章，js性能优化-利用备忘模式进行结果缓存; 如此一来，我们就可以很快得到结果了

function memorize (fn) {
  const cache = {}
  return function(){
    const args = [].slice.call(arguments)
    const key = JSON.stringify(args)
    return cache[key] || (cache[key] = fn.apply(fn, args))
  }
}

const fib = n => {
  const F = n => {
    if(n === 1 || n === 0) {
      return n
    }
    let res = F(n-1) + F(n-2)
    return res % 1000000007
  }
  const cacheF = memorize(F)
  return cacheF(n)
}

再次提交运行，发现还是超时，再看看代码，其实

const cacheF = memorize(F)

这句话只是缓存了F这个函数，而F内部又递归调用了F，内部的F并没有被缓存到！
现在看这个memorize函数对存在内部自调用的方法无可奈何了，也算是备忘录模式的一个缺陷吧。但是，这个缓存的思想我们是可以提取出来的：

const fib = n => {
  const map = {}
  const F = n => {
    if(n === 1 || n === 0) {
      return n
    }
    if (map[n]) return map[n];
    let res = F(n-1) + F(n-2)
    return res % 1000000007
  }
  return F(n)
}

这样在递归调用自身的之前先判断有没有缓存，有就直接返回结果，避免再次调用耗时。

提交！通过！

提交通过.png

嗯，不错，当我沾沾自喜的时候，突然感觉，就这？有没有更好的办法，除了递归外还有其他更好的办法吗？？？

答案是有的，上面的解法：（递归 + 缓存优化） 虽然还可以，但也有个缺点：缓存需要使用 O(N) 的额外空间

我也想不出更好办法，于是看了题解，还有一种最适合的方法：动态规划！

• 动态规划的解法
  首先我们先回忆一下（递归 + 缓存优化）解法，它的缺点就是需要O(N) 的额外空间，那么利用动态规划去解决这个缺点就不能用递归了，因为你用递归的话，还是要缓存来解决时间复杂度的问题。那么要怎么解决呢？

首先，我们知道F(n) = F(n-1) + F(n-2), 并且只知道初始的F(0) = 0; F(1) = 1; 对于后面的数字n,要求其解的话，只能从n-1, n-2 , n-3一个个去往回推算来求，而这个过程又会存在重复计算的问题！既然这样子不好，那么可不可以从前面开始 ：0，1，2，3，4 ... n 这样子往后面推算呢？所以思路如下，0，1我们是知道的，那么就从2开始算，2，3，4，... n 采用循环一个个去算，并且后面的结果依赖前面的计算结果，这样子只要一个循环下来，从2到n就能求解成功了！上代码：

const fib = n => {
  if (n === 0 || n === 1) return n
  let a = 0; // a相当于  F(n-2)的 n - 2
  let b = 1; // b相当于  F(n-1)的 n - 1
  let sum = 0;
  for (let i = 2; i <= n; i++) {
    sum = (a + b) % 1000000007;
    a = b; // 为下一数字准备
    b = sum; // 为下一个数字准备
  }
  return sum
}

从上面的代码可以看出，a代表了n-2, b代表了 n-1 , sum代表了n的解，随着i的前进， a, b也在前进。如此一来后面的数字依赖前面的解，环环相扣，只需要从2循环到n就能求出n的解。时间复杂度O(N) ；而空间复杂度呢，因为只用了a b sum 3个变量，可以看作是O(1)； 而这个过程就是动态规划！

怎么理解动态规划

我的理解就是a\b\sum是固定变量，但是随着循环递增会不断的基于该空间复杂度不变而去不断的变化其值，这就是动态规划！

一个时间复杂度O(N) 空间复杂度O(1)的解法，确实是最优解了，再优你也达不到时间复杂度O(1) 空间复杂度度O(1); 因为那样子的话就不用计算了。

扩展

与此题相似的题目还有一道青蛙跳台阶的问题，我刚看的时候也是没有想到是斐波那契数列，得从后往回推才反应过来，实在是巧妙。题目如下：来源

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

我们容易从第一个台阶开始算这个青蛙可能会有几种跳法，这样子很难想象去求解。所以这里应该从后面往回推，如下图所说：

青蛙跳台阶

其实这题很多人和我一样没有把它转换为斐波那契数列。所以想通之后，最终还是同样的解法，只不过最开始f(0)、 f(1)的值稍有变化罢了。