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;
}

复杂度

• 时间：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
• 滚动变量注意 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)

关联题

• 同套路：70. 爬楼梯 —— 同款递推，初始值不同
• 进阶：746. 使用最小花费爬楼梯 —— 带 cost 的变式
• 知识点：DP 入门 + 滚动变量优化见动态规划