07、斐波那契数
大约 5 分钟数据结构算法算法基地面试动态规划刷题程序厨校招社招
哈喽，大家好，我是厨子，今天给大家说一下经典题目斐波那契
https://leetcode.cn/problems/fibonacci-number/
题目描述
斐波那契数（通常用 F(n) 表示）形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n，请计算 F(n)。
示例 1:
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2:
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3:
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3
约束条件:
0 <= n <= 30
什么是斐波那契数列？
斐波那契数列的定义
斐波那契数列：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...
规律：
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
...
每个数都是前两个数之和
斐波那契数列的特点
特点1: 递归定义
每个数由前两个数相加得到
特点2: 增长迅速
后面的数字增长速度很快
递归树可视化
计算 F(5) 的递归树：
F(5)
/ \
F(4) F(3)
/ \ / \
F(3) F(2) F(2) F(1)
/ \ / \ / \
F(2) F(1) F(1) F(0) F(1) F(0)
/ \
F(1) F(0)
问题：大量重复计算！
F(3) 被计算了 2 次
F(2) 被计算了 3 次
F(1) 被计算了 5 次
F(0) 被计算了 3 次
→ 需要优化！使用动态规划
解题思路
方法对比
方法一：递归（暴力）
核心思想
直接按照定义递归计算，但会有大量重复计算。
代码实现
class Solution {
public:
int fib(int n) {
// 基本情况
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
// 递归情况
return fib(n - 1) + fib(n - 2);
}
};
时间复杂度: O(2^n)，指数级增长
空间复杂度: O(n)，递归栈深度
缺点:
- 大量重复计算
- 时间复杂度太高
n 稍大就会超时
方法二：记忆化递归（Top-Down DP）
核心思想
使用哈希表或数组缓存已计算的结果，避免重复计算。
代码实现
class Solution {
public:
int fib(int n) {
// 创建记忆数组，-1 表示未计算
vector<int> memo(n + 1, -1);
return fibHelper(n, memo);
}
private:
int fibHelper(int n, vector<int>& memo) {
// 基本情况
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
// 如果已经计算过，直接返回缓存结果
if (memo[n] != -1) {
return memo[n];
}
// 计算并缓存结果
memo[n] = fibHelper(n - 1, memo) + fibHelper(n - 2, memo);
return memo[n];
}
};
时间复杂度: O(n)，每个 F(i) 只计算一次
空间复杂度: O(n)，记忆数组 + 递归栈
方法三：动态规划（Bottom-Up DP）⭐
核心思想
使用自底向上的方法，从 F(0) 和 F(1) 开始逐步计算到 F(n)。
DP 五部曲
1. 确定 dp 数组及下标含义
dp[i] 表示第 i 个斐波那契数的值
2. 确定递推公式
dp[i] = dp[i-1] + dp[i-2]
3. dp 数组如何初始化
dp[0] = 0
dp[1] = 1
4. 确定遍历顺序
从前往后遍历，i 从 2 到 n
5. 举例推导 dp 数组
n = 5
dp[0] = 0
dp[1] = 1
dp[2] = 1
dp[3] = 2
dp[4] = 3
dp[5] = 5 ✓
详细图解示例
计算 F(5)：
步骤1: 初始化
dp[0] = 0
dp[1] = 1
dp = [0, 1, ?, ?, ?, ?]
步骤2: 计算 dp[2]
dp[2] = dp[1] + dp[0] = 1 + 0 = 1
dp = [0, 1, 1, ?, ?, ?]
步骤3: 计算 dp[3]
dp[3] = dp[2] + dp[1] = 1 + 1 = 2
dp = [0, 1, 1, 2, ?, ?]
步骤4: 计算 dp[4]
dp[4] = dp[3] + dp[2] = 2 + 1 = 3
dp = [0, 1, 1, 2, 3, ?]
步骤5: 计算 dp[5]
dp[5] = dp[4] + dp[3] = 3 + 2 = 5
dp = [0, 1, 1, 2, 3, 5]
结果: dp[5] = 5 ✓
代码实现
class Solution {
public:
int fib(int n) {
// 特殊情况处理
if (n <= 1) {
return n;
}
// 创建 dp 数组
vector<int> dp(n + 1);
// 初始化
dp[0] = 0;
dp[1] = 1;
// 状态转移
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
// 返回结果
return dp[n];
}
};
时间复杂度: O(n)，遍历一次数组
空间复杂度: O(n)，dp 数组
这里我们的空间复杂度是 O(n)，我们是否可以对其进一步优化呢？
方法四：动态规划空间优化⭐⭐
核心思想
观察状态转移方程 dp[i] = dp[i-1] + dp[i-2]，发现当前状态只依赖前两个状态，所以只需要两个变量即可。
代码实现
class Solution {
public:
int fib(int n) {
// 特殊情况
if (n <= 1) {
return n;
}
// 只需要两个变量存储前两个斐波那契数
int prev2 = 0; // F(i-2)
int prev1 = 1; // F(i-1)
// 从 F(2) 开始计算
for (int i = 2; i <= n; i++) {
int curr = prev1 + prev2; // F(i) = F(i-1) + F(i-2)
// 滚动更新
prev2 = prev1; // 旧的 F(i-1) 变成新的 F(i-2)
prev1 = curr; // F(i) 变成新的 F(i-1)
}
return prev1;
}
};
更简洁的写法
class Solution {
public:
int fib(int n) {
if (n <= 1) return n;
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
int sum = a + b;
a = b;
b = sum;
}
return b;
}
};
时间复杂度: O(n)
空间复杂度: O(1)，只用两个变量
