斐波那契数列

问题

实现斐波那契数列：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)。

经典应用是爬楼梯问题：每次可以爬 1 或 2 个台阶，爬到第 n 阶有多少种方法？

解答

递归（会超时）

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

时间复杂度 O(2^n)，存在大量重复计算。

记忆化递归

function fib(n, memo = {}) {
  if (n <= 1) return n;
  
  // 已计算过，直接返回
  if (memo[n] !== undefined) return memo[n];
  
  // 计算并缓存结果
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

console.log(fib(50)); // 12586269025

动态规划

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

console.log(fib(10)); // 55

空间优化

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

console.log(fib(10)); // 55

爬楼梯问题

// 爬到第 n 阶的方法数 = 爬到第 n-1 阶的方法数 + 爬到第 n-2 阶的方法数
function climbStairs(n) {
  if (n <= 2) return n;
  
  let prev = 1; // 1 阶：1 种方法
  let curr = 2; // 2 阶：2 种方法
  
  for (let i = 3; i <= n; i++) {
    const next = prev + curr;
    prev = curr;
    curr = next;
  }
  
  return curr;
}

console.log(climbStairs(5)); // 8

关键点

• 递归解法直观但时间复杂度是 O(2^n)，会超时
• 记忆化递归用空间换时间，避免重复计算
• 动态规划自底向上，时间 O(n)，空间 O(n)
• 只需要前两个值，空间可优化到 O(1)
• 爬楼梯本质就是斐波那契，F(n) = F(n-1) + F(n-2)