509. 斐波那契数
题目描述
斐波那契数列的前两项是 F(0) = 0、F(1) = 1，从第 2 项起每一项等于它前面两项相加，即 F(n) = F(n - 1) + F(n - 2)。
输入整数 n，返回 F(n)。
示例 1
输入：n = 2 输出：1
解释：F(2) = 1 + 0 = 1。
示例 2
输入：n = 3 输出：2
解释：F(3) = 1 + 1 = 2。
示例 3
输入：n = 4 输出：3
解释：F(4) = 2 + 1 = 3。
数据范围
0 <= n <= 30
解题思路：动态规划（滚动变量）
直接递归会把同一个 F(k) 重复算指数次。反过来从小到大递推：算 F(i) 只需要前两项，所以只用两个变量 a、b 分别保存 F(i-2) 和 F(i-1)，每轮向前滚动一位。
为什么正确
第 i 轮结束时 a = F(i-1)，b = F(i)。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
更新顺序要小心：先写 a = b 再写 b = a + b 会用到已被覆盖的 a。Python 用同时赋值 a, b = b, a + b，其他语言先存临时变量。n = 0 和 n = 1 要直接返回。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def fib(self, n: int) -> int:
if n < 2:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return bclass Solution {
public int fib(int n) {
if (n < 2) {
return n;
}
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
int c = a + b;
a = b;
b = c;
}
return b;
}
}class Solution {
public:
int fib(int n) {
if (n < 2) {
return n;
}
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
int c = a + b;
a = b;
b = c;
}
return b;
}
};func fib(n int) int {
if n < 2 {
return n
}
a, b := 0, 1
for i := 2; i <= n; i++ {
a, b = b, a+b
}
return b
}var fib = function(n) {
if (n < 2) {
return n;
}
let a = 0, b = 1;
for (let i = 2; i <= n; i++) {
[a, b] = [b, a + b];
}
return b;
};function fib(n: number): number {
if (n < 2) {
return n;
}
let a = 0, b = 1;
for (let i = 2; i <= n; i++) {
[a, b] = [b, a + b];
}
return b;
}其他解法
滚动变量的递推最简单，是线性时间；矩阵快速幂把线性递推转化为矩阵乘方，时间降到 O(log n)。
解法 2：矩阵快速幂 时间 O(log n)，空间 O(1)
把递推写成矩阵形式：[[F(n+1), F(n)], [F(n), F(n−1)]] = [[1, 1], [1, 0]] 的 n 次方。用快速幂按 n 的二进制位累乘，只需 O(log n) 次 2×2 矩阵乘法，结果矩阵右上角就是 F(n)。
复杂度是对数级，适用于 n 极大且需要取模的场合，也能推广到任意线性递推。本题 n ≤ 30，优势体现不出来，代码也更长。
class Solution:
def fib(self, n: int) -> int:
# [[F(n+1), F(n)], [F(n), F(n-1)]] = [[1, 1], [1, 0]]^n
def mul(a, b):
return [[a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
[a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]]]
res = [[1, 0], [0, 1]]
base = [[1, 1], [1, 0]]
while n:
# 快速幂：按 n 的二进制位累乘
if n & 1:
res = mul(res, base)
base = mul(base, base)
n >>= 1
return res[0][1]class Solution {
private long[][] mul(long[][] a, long[][] b) {
long[][] c = new long[2][2];
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
return c;
}
public int fib(int n) {
long[][] res = {{1, 0}, {0, 1}}, base = {{1, 1}, {1, 0}};
while (n > 0) {
if ((n & 1) == 1) res = mul(res, base);
base = mul(base, base);
n >>= 1;
}
return (int) res[0][1];
}
}class Solution {
public:
using M = array<array<long long, 2>, 2>;
M mul(const M& a, const M& b) {
M c{};
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
return c;
}
int fib(int n) {
M res{{{1, 0}, {0, 1}}}, base{{{1, 1}, {1, 0}}};
while (n) {
if (n & 1) res = mul(res, base);
base = mul(base, base);
n >>= 1;
}
return res[0][1];
}
};func fib(n int) int {
mul := func(a, b [2][2]int) [2][2]int {
var c [2][2]int
for i := 0; i < 2; i++ {
for j := 0; j < 2; j++ {
c[i][j] = a[i][0]*b[0][j] + a[i][1]*b[1][j]
}
}
return c
}
res := [2][2]int{{1, 0}, {0, 1}}
base := [2][2]int{{1, 1}, {1, 0}}
for n > 0 {
if n&1 == 1 {
res = mul(res, base)
}
base = mul(base, base)
n >>= 1
}
return res[0][1]
}var fib = function(n) {
const mul = (a, b) => [
[a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
[a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]],
];
let res = [[1, 0], [0, 1]], base = [[1, 1], [1, 0]];
while (n > 0) {
if (n & 1) res = mul(res, base);
base = mul(base, base);
n >>= 1;
}
return res[0][1];
};function fib(n: number): number {
const mul = (a: number[][], b: number[][]): number[][] => [
[a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
[a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]],
];
let res = [[1, 0], [0, 1]], base = [[1, 1], [1, 0]];
while (n > 0) {
if (n & 1) res = mul(res, base);
base = mul(base, base);
n >>= 1;
}
return res[0][1];
}