【Daily Interview】- 08 斐波那契数

题目

!! 题目来源：斐波那契数 - 力扣

分析

对于大名鼎鼎的斐波那契数列，相信大家并不陌生，简单来说，就是斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

那么最简单暴力的思路就是递归：

• 首先判断边界情况：当 n == 0 或者 n == 1 的时候，结束递归，返回 n
• 否则返回 fib(n - 1) + fib(n - 2)

具体代码如下：

const fib = function (n) {
  if (n === 0 || n === 1) {
    return n;
  } else {
    return fib(n - 1) + fib(n - 2);
  }
};

结果如下：

事实上，虽然这个思路简单直接，但其算法复杂度是非常高的，即便题目限制了 n 的范围，计算的时候，依然等了好一会儿才算到结果（递归深度与 n 直接相关）。

优化

如两数之和中提到的思路：通常优化时间复杂度的方案是用空间换时间。

这里我们同样可以创建一个 cache 来进行优化：

• 首先遍历 n，将 0 和 1 直接存入 cache 中
• 随后依次计算出当前 n 的值，存入 cache 中
• 当循环结束之后，cache 其实已经是一个完整的斐波那契数列了，而对于题目，我们返回 cache[n] 即可

具体代码如下：

const fib = function (n) {
  const cache = [];
  for (let i = 0; i <= n; i++) {
    if (i === 0 || i === 1) {
      cache[i] = i;
    } else {
      cache[i] = cache[i - 1] + cache[i - 2];
    }
  }
  return cache[n];
};

结果如下：