509.斐波那契数

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

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

示例：

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

// 递归
function fibonacci(n) {
  // 边界
  if (n <= 0) return 0;

  return n <= 2 ? 1 : fibonacci(n - 2) + fibonacci(n - 1);
}

// 动态规划 - 保存结果
function fibonacci(n) {
  // 边界
  if (n <= 0) return 0;
  if (n === 1 || n === 2) return 1;
  // 循环
  const res = [1, 1];
  for (let i = 2; i < n; i++) {
    const cur = res[i - 2] + res[i - 1];
    res.push(cur);
  }
  return res[n - 1];
}

// 动态规划 - 滚动数组
function fibonacci(n) {
  // 边界
  if (n <= 0) return 0;
  if (n === 1 || n === 2) return 1;
  // 循环
  let p = 0,
    q = 0,
    r = 1;
  for (let i = 2; i <= n; i++) {
    p = q;
    q = r;
    r = p + q;
    console.log(">>>:", p, q, r);
  }
  return r;
}