1. 题目描述

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

  1. F(0) = 0,   F(1) = 1
  2. F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

给定 N，计算 F(N)。
示例 1：

  1. 输入：2
  2. 输出：1
  3. 解释：F(2) = F(1) + F(0) = 1 + 0 = 1.

示例 2：

  1. 输入：3
  2. 输出：2
  3. 解释：F(3) = F(2) + F(1) = 1 + 1 = 2.

示例 3：

  1. 输入：4
  2. 输出：3
  3. 解释：F(4) = F(3) + F(2) = 2 + 1 = 3.

2. 解题思路

（1）暴力递归：最简单的方式就是递归，根据题目中给出的斐波那契数列公式进行递归遍历。这种方式存在重复调用计算的问题。

  • 时间复杂度：O(n**2**)
  • 空间复杂度：O(1)

（2）递归 + 缓存：由于递归在遍历的过程中，存在很多节点重复计算的情况，所以我们可以将每次求的值进行缓存，以便于后面计算时使用。这里我们使用闭包来缓存每次计算的值。

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

（3）动态规划：这里使用了动态规划，本质上也是在对已经计算好的结果进行缓存，只不过不用递归了，而是显式的进行迭代。

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

（4）动态规划：这里使用了动态规划，我们发现每次计算fib(N)，只需要用到fib(N-1)和fib(N-2)，所以只需要使用两个变量来缓存就好了。

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

    3. 代码实现

    （1）暴力递归
    1. /**
    2. * @param {number} N
    3. * @return {number}
    4. */
    5. var fib = function(N) {
    6.   if (N < 1) return 0
    7.   if (N === 1 || N === 2) return 1;
    8.   return fib(N - 1) + fib(N - 2);
    9. };
    （2）递归 + 缓存
    1. var fib = (function(N) {
    2.  if (N === 1 || N === 2) return 1;
    3.  let arr = [0,1,1]
    4.  return N => {
    5.      if(N<arr.length){
    6.          return arr[N]
    7.      }
    8.      for(let i = arr.length; i <= N; i++){
    9.          arr[i] = arr[i-1] + arr[i-2]
    10.      }
    11.      return arr[N]
    12.  }
    13. })();
    （3）动态规划
    1. /**
    2. * @param {number} N
    3. * @return {number}
    4. */
    5. var fib = function(N) {
    6.   if (N < 1) return 0
    7.   if (N === 1 || N === 2) return 1;
    8.   let pre = 1, cur = 1, sum = 0; // pre前一位数字的累加和, cur当前数字, sum当前数字的累加和
    9.   for (let i = 3; i <= N; i++) {
    10.       sum = pre + cur;
    11.       pre = cur;
    12.       cur = sum;
    13.   }
    14.   return cur;
    15. };
    （4）动态规划
    1. /**
    2. * @param {number} N
    3. * @return {number}
    4. */
    5. var fib = function(N) {
    6.  if (N < 1) return 0
    7.  if (N === 1 || N === 2) return 1;
    8.  const res = [0,1]
    9.  for(let i= 2; i <= N; i++){
    10.     res[i] = res[i-1] + res[i-2]
    11.  }
    12.  return res[N]
    13. };

    4. 提交结果

    （1）暴力递归
    image.png
    （2）递归 + 缓存
    image.png
    （3）动态规划
    image.png
    （4）动态规划
    image.png