斐波那契数列（Fibonacci Sequence）
斐波那契数列是理解递归树、重叠子问题和动态规划优化的经典入门例子。
定义
斐波那契数列通常定义为：
fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2), n >= 2
也有资料从 fib(1) = 1, fib(2) = 1 开始定义，本质只是下标约定不同。
核心价值
| 视角 | 说明 |
|---|---|
| 递归入门 | 数学定义可以直接翻译成递归函数 |
| 递归树 | 暴力递归会展开成二叉递归树 |
| 重叠子问题 | fib(n - 2) 等子问题会被重复计算 |
| 动态规划 | 通过备忘录或 DP table 消除重复计算 |
| 空间压缩 | 当前状态只依赖前两个状态，可优化到 O(1) 空间 |
基本实现
暴力递归
int fib(int n) {
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
这个写法最贴近定义，但存在大量重复计算，时间复杂度为 O(2^n)。
动态规划
int fib(int n) {
if (n < 2) {
return n;
}
int prev = 0;
int curr = 1;
for (int i = 2; i <= n; i++) {
int next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}
迭代 DP 将时间复杂度降为 O(n)，并通过只保留前两个状态将空间复杂度降为 O(1)。
与动态规划的关系
斐波那契数列严格来说不是“求最值”问题，但它非常适合展示 动态规划 的两个关键优化点：
- 暴力递归会产生重叠子问题
- 备忘录或 DP table 可以保证每个子问题只计算一次
因此它常作为动态规划入门例子，用来建立“递归定义 → 状态转移 → 消除重复计算”的思维。
时间复杂度
| 实现方式 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力递归 | O(2^n) | O(n) | 递归树大量重复计算 |
| 备忘录递归 | O(n) | O(n) | 每个子问题只计算一次 |
| DP table | O(n) | O(n) | 自底向上填表 |
| 状态压缩 | O(n) | O(1) | 只保留前两个状态 |
应用场景
- 理解 递归 的分解问题思维
- 理解动态规划中的重叠子问题
- 对比自顶向下备忘录和自底向上 DP table
- 作为 LeetCode 509、70 等题目的基础模型
相关概念
- 递归：斐波那契数列的定义天然适合递归表达
- 动态规划：通过备忘录或 DP table 优化重复计算
- 分治算法：同样属于分解问题思维，但普通分治通常不强调重叠子问题
- 时间复杂度：暴力递归与 DP 解法复杂度差异明显
参考资料
- 理解递归框架：用斐波那契数列解释分解问题思维
- 动态规划框架：用斐波那契数列解释重叠子问题与 DP 优化
- 分治算法解题套路框架：用斐波那契数列说明分解问题思想