LeetCode 509. 斐波那契数
题目描述
题意分析
斐波那契数列的下标从零开始，
F(0) = 0、F(1) = 1，当n >= 2时，F(n) = F(n - 1) + F(n - 2)。给定下标n，只需要返回这一项的数值，不需要输出整条数列。初始两项决定了整个数列，不能把它们替换为其他题目的初值。本题的
n不超过30，按定义从小到大逐项计算即可，结果也在普通整数范围内。
解法：滚动变量递推
核心思路
[!blue]
直接按公式递归，会在计算相邻两项时反复求解许多相同的更小项。既然每一项只依赖更早的两项，就按下标递增计算：轮到某一项时，它所需的两个值已经得到，不必再次展开递归。
若用数组保存全部
F(0)..F(n)，递推本身很直接，但计算F(i)时实际上只读取F(i - 2)和F(i - 1)，更早的项以后都不会再用到。因此只保留两个滚动变量prev2和prev1就足够。在第
i轮开始前，约定prev2 = F(i - 2)、prev1 = F(i - 1)。先计算二者之和得到F(i)，然后把旧的prev1移给prev2，把新结果移给prev1。更新后两个变量正好保存F(i - 1)、F(i)，符合下一轮的要求。循环从
i = 2开始，所以初始值必须是0和1。n为零或一时根本不需要递推，直接返回n；其他情况计算到第n项后，最新的prev1就是答案。
解题步骤
- 若
n < 2，直接返回n，处理两个已知初始项。- 初始化
prev2 = 0、prev1 = 1，分别代表第零项和第一项。- 从
i = 2到n，先计算旧的两个变量之和。- 将两个变量整体向前推进一项：
prev2接收旧prev1，prev1接收新和。- 循环结束，返回保存第
n项的prev1。
代码实现
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)。每个下标从二到n只计算一次，每轮执行常数次运算。- 空间复杂度：
O(1)。仅保存相邻两项及当前和，不需要数组或递归调用栈。
关键点总结
[!green]
- 递推顺序对应依赖顺序，先得到小下标项，再计算大下标项，避免重复求值。
- 滚动变量能够替代数组，是因为下一项始终只依赖最近两项。
- 初值、循环起点和返回变量必须共同符合每轮开始前的状态定义。
易错点总结
[!yellow]
- 忽略
n = 0的入口：不执行循环时若直接返回初始化的prev1，会错误返回一。- 初始两项都设成一：这不符合本题从下标零开始的定义，后续数值都会偏移。
- 先覆盖
prev2再计算和：会丢掉旧的第i - 2项。Java 先保存current；Go 的多重赋值会先计算所有右侧表达式。- 循环没有包含
n：只计算到n - 1会少求一项，条件应为i <= n。- 返回
prev2：循环结束时它保存的是上一项，答案在prev1中。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 70. 爬楼梯 | 简单 | 递推关系相近但初值不同，不能因为都依赖前两项就直接共用返回值。 |
| 1137. 第 N 个泰波那契数 | 简单 | 把依赖前两项扩展为前三项，滚动变量的数量随依赖宽度变化。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！