0509. Fibonacci Number¶
题目信息¶
- 题号:
0509
- 难度:
Easy
- 主题:
递推序列、两个基例、非负下标
- 原题:
- 重点:
F(0)=0、F(1)=1、从 F(2) 起等于前两项之和、输入是序列下标
题目重述¶
斐波那契数列定义为 F(0) = 0、F(1) = 1,并且对所有 n >= 2,有 F(n) = F(n - 1) + F(n - 2)。给定整数 n,返回 F(n)。
n 位于 [0, 30]。需要特别保留 n = 0 和 n = 1 两个基例;返回的是第 n 项的数值,而不是前 n 项列表。
自建示例¶
普通递推项:
输入:n = 7
输出:13
解释:数列从 F(0) 开始依次为 0、1、1、2、3、5、8、13,因此 F(7)=13。
零下标基例:
输入:n = 0
输出:0
解释:定义直接规定 F(0)=0。
只保留相邻两项¶
递推关系在计算第 i 项时只需要前两项,因此不必保存完整数组。初始化 a = F(0)、b = F(1),每轮令新项为 a + b,再向前移动两个变量;n 为 0 或 1 时直接返回定义值。
C++ 实现¶
class Solution {
public:
int fib(int n) {
if (n < 2) return n;
int previous = 0;
int current = 1;
for (int i = 2; i <= n; ++i) {
int next = previous + current;
previous = current;
current = next;
}
return current;
}
};
代码分析¶
循环不变量是 previous = F(i-2)、current = F(i-1),更新后得到下一项且不改变定义基例。时间复杂度为 O(n),额外空间复杂度为 O(1)。