跳转至

509. 斐波那契数（Fibonacci Number）

频次 ★★★ · 难度 🟢 · 高频：全厂

题目

计算第 n 个斐波那契数 F(n)，F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。

示例： 

输入: n = 4
输出: 3  （F(0)=0, F(1)=1, F(2)=1, F(3)=2, F(4)=3）

思路

DP 三部曲：定义 dp[i] = 第 i 个斐波那契数；递推 dp[i] = dp[i-1] + dp[i-2]；压缩到 O(1) 空间（滚动变量）。

也是 DP 入门题，演示"如何从递归到 DP 到空间优化"。

代码

// DP 滚动变量 O(n) / O(1)
public int fib(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;          // F(0), F(1)
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

DP 五部曲自查表（509 = 空白模板，每题照此自问）

步 问题 509 答案
① 状态定义 dp[i] 是什么（一句话说死，含"以…/前 i 个"约束） dp[i] = F(i) 本身
② 转移方程 从哪些更小状态来 dp[i] = dp[i-1] + dp[i-2]（递归式抄题即转移）
③ 初始化 递推算不出的地基 dp[0]=0、dp[1]=1（新手常错成 dp[1]=0 → 全表错位）
④ 遍历顺序 保依赖就绪 i 从 2 起（dp[-1] 不存在，0/1 已手工）
⑤ 手推验证 拿小 case 对 F(4)：0,1,1,2,3

三种实现的面试口答三连

  1. 朴素递归 O(2ⁿ)：F(30) 重复计算十亿次级——不可交
  2. 记忆化递归 O(n)/O(n)：自顶向下，Map 缓存——同一个"状态+转移"
  3. 迭代 DP O(n)：自底向上，dp 数组可滚动 O(1)（微博中 a,b 双变量，53 的 curSum/maxSum 是同手法）

工具坑：computeIfAbsent 里递归改自身

HashMap 的 computeIfAbsent(lambda) 在计算期间持有内部锁，lambda 里递归再往同一个 map 塞值 → ConcurrentModificationException。记忆化递归写 Map 必须老老实实 containsKey 检查 + put（本章骨架已实测验证过这个坑）。

复杂度

  • 时间：O(n)
  • 空间：O(1)

边界条件

  • n = 0：返回 0
  • n = 1：返回 1
  • n 较大（如 ≤ 30）：直接迭代；n 极大时需矩阵快速幂 O(log n)

变式

  • 70. 爬楼梯：实质是斐波那契（dp[1]=1, dp[2]=2）
  • 矩阵快速幂：O(log n) 解法，面试中提一句证明见识

易错点

  • 递归写法指数爆炸（O(2^n)），面试中不要直接写递归，用迭代或记忆化
  • 滚动变量注意 a, b 的初始值——F(0)=0, F(1)=1

面试追问

  • 如何用 O(log n) 解？ 矩阵快速幂：[[F(n), F(n-1)],[F(n-1), F(n-2)]] = [[1,1],[1,0]]^(n-1)
  • 递归加记忆化怎么写？ 用 HashMap 或数组保存已计算的值，时间 O(n) 空间 O(n)

关联题