斐波那契数

leetcode-题目

解法一：暴力递归

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

解法二：带备忘录的递归

解法一存在的问题是存在大量的重复计算，即重叠子问题。

let helper = {};
let fib = function (n) {
  if (n === 0) return 0;
  if (n === 1) return 1;
  if (helper[n]) return helper[n];
  let sum = fib(n - 1) + fib(n - 2);
  helper[n] = sum;
  return sum;
};

解法三：使用状态压缩的技巧

let fib = function (n) {
  if (n === 0) return 0;
  if (n === 1 || n === 2) return 1;
  let prev = 1;
  let curr = 1;
  for (let i = 3; i <= n; i++) {
    let sum = prev + curr;
    prev = curr;
    curr = sum;
  }
  return curr;
};