算法-斐波那契数列

方式1

var fib = function (n) {
  if (n === 0 || n === 1) {
    return n;
  }
  const v = fib(n - 1) + fib(n - 2);
  return v % 1000000007;
};

方式2

/**
 * 利用数组空间进行存储，空间复杂度O(n)
 */
const fib = (n, arr = []) => {
  if (n === 0 || n === 1) {
    return n;
  }
  let first = arr[n - 1];
  let second = arr[n - 2];
  if (!first) {
    first = arr[n - 1] = fib(n - 1, arr);
  }
  if (!second) {
    second = arr[n - 2] = fib(n - 2, arr);
  }

  return (first + second) % 1000000007;
};

方式3

// 0 1 2 3 4
// 0 1 1 2 3   :    0 1 1 =>  1 1 2 => 1 2 3 => 2 3 5
const fib2 = (n) => {
  if (n === 0 || n === 1) {
    return n;
  }

  let a = 0,
    b = 1,
    sum = a + b;

  // n:2 应为1 : 1 1 2
  // n:3应为2: 1 2 3
  for (let i = 2; i <= n; i++) {
    a = b;
    b = sum;
    sum = (a + b) % 1000000007;
  }
  return b;
};