LeetCode 509. 斐波那契数
目录
题目描述
题意分析
题目给出一个完整的定义：
F(0) = 0，F(1) = 1，当n >= 2时F(n) = F(n - 1) + F(n - 2)，要求返回第n项的值。定义已经写死，不需要自己推导递推式，真正被考察的是怎么把这条递推落地。
约束信号很明确：n的上限只有 30，结果远小于int的范围，既不会溢出也不要求取模；这么小的规模说明出题人在意的不是极限效率，而是代码是否干净、初值是否摆对、有没有多余的空间开销。
边界只有两个：n = 0必须返回0，n = 1必须返回1，这两项是定义给的基准值，不能靠递推算出来；从n = 2起才进入累加。
还要注意起点约定：这里的首项是0而不是1，和「爬楼梯」那类以1开头的数列只差一个位移，混淆之后每个答案都会整体错开一位。
解法：滚动变量递推
核心思路
递推式已经给出：
F(i) = F(i - 1) + F(i - 2)。直接递归虽然贴近定义，但会重复计算相同子问题；例如计算F(5)时，F(3)会从两条递归分支再次展开，时间复杂度呈指数增长。自底向上计算可以让每个状态只求一次。进一步观察，求
F(i)时只需要前两项，更早的结果不会再被访问，因此无需保存完整dp数组，只保留两个滚动变量：
prev2 = F(i - 2)；prev1 = F(i - 1)。这是每轮开始时的不变量。先计算
current = prev2 + prev1 = F(i)，再把窗口整体向前移动一格，不变量便对下一轮继续成立。初始化prev2 = F(0) = 0、prev1 = F(1) = 1，循环结束后prev1正好是F(n)，因此算法正确。
解题步骤
- 当
n < 2时直接返回n，覆盖F(0)和F(1)。- 初始化
prev2 = 0、prev1 = 1。- 从
i = 2遍历到n，计算current = prev2 + prev1。- 更新
prev2 = prev1、prev1 = current，让两个变量继续表示下一轮所需的前两项。- 循环结束后返回
prev1。以
n = 5为例，两个变量依次表示(F(0), F(1)) = (0, 1)、(F(1), F(2)) = (1, 1)、(F(2), F(3)) = (1, 2)、(F(3), F(4)) = (2, 3)、(F(4), F(5)) = (3, 5)，最终返回5。
代码实现
class Solution {
public int fib(int n) {
if (n < 2) {
return n;
}
int prev2 = 0;
int prev1 = 1;
for (int i = 2; i <= n; i++) {
int current = prev2 + prev1;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
}
func fib(n int) int {
if n < 2 {
return n
}
prev2, prev1 := 0, 1
for i := 2; i <= n; i++ {
prev2, prev1 = prev1, prev2+prev1
}
return prev1
}
复杂度分析
- 时间复杂度：
O(n)。从2到n各计算一次。- 空间复杂度：
O(1)。只维护两个历史状态和当前结果。
关键点总结
- 朴素递归的问题是重复子问题；改为递推后，每个
F(i)只计算一次。- 当状态转移只依赖固定数量的前项时，可以用滚动变量替代完整数组。
- 初始化必须与循环不变量对应：第一轮
i = 2前保存的应是F(0)和F(1)。- 面试时可按“递归 -> 记忆化 -> DP 数组 -> 滚动变量”说明优化过程；若追问超大
n，再讨论快速倍增或矩阵快速幂，而非为本题约束增加复杂度。
易错点总结
- 忘记单独处理
n = 0：循环不会执行，若直接返回初始的prev1会错误得到1。- 初值写成
1, 1会套成爬楼梯的状态，使F(2)错误等于2。- 循环条件要包含
n；写成i < n会少算一项。- 更新变量时不能覆盖仍要参与计算的旧值。Java 需要先保存
current；Go 的并行赋值会先计算右侧，因此可以直接滚动。- 循环结束应返回最新状态
prev1，返回prev2会得到F(n - 1)。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 70. 爬楼梯 | 简单 | 同一条递推，初值改为 1 和 1，整体比本题右移一位 |
| 746. 使用最小花费爬楼梯 | 简单 | 转移里带权重，取两条来路的最小值而不是求和 |
| LCR 088. 使用最小花费爬楼梯 | 简单 | 与 746 同题换编号，适合复查初值与终点的处理 |
| 剑指 Offer 10- I. 斐波那契数列 | 简单 | 数列相同但要对 1e9 + 7 取模，需在每步累加后取模 |
| 剑指 Offer 10- II. 青蛙跳台阶问题 | 简单 | 爬楼梯加取模，起点计数约定 F(0) = 1 是易错处 |
| 面试题 08.01. 三步问题 | 简单 | 依赖前三项，滚动变量从两个扩到三个 |
| 补充题 2. 圆环回原点问题 | 中等 | 状态多一维「当前所处顶点」，环形转移下的滚动数组 |