LeetCode-Book 509. 斐波那契数：暴力递归、记忆化与动态规划的状态压缩全解-开发者社区

LeetCode-Book 509. 斐波那契数：暴力递归、记忆化与动态规划的状态压缩全解

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book

本篇技术指南以 LeetCode-Book 仓库《Krahets 笔面试精选 88 题》中 509. 斐波那契数为核心骨架，系统讲解斐波那契数列的三种解法演进路径（暴力搜索 → 记忆化递归 → 动态规划），并深入剖析动态规划的状态压缩原理与三语言实现。读完本文，你将掌握"重叠子问题"的识别方法、动态规划的四个标准步骤（状态定义、转移方程、初始状态、返回值），以及如何把 $O(N)$ 空间的 DP 表压缩为 $O(1)$ 空间的滚动变量，为后续学习爬楼梯、打家劫舍等经典 DP 题目打下基础。

题目背景与数列定义

斐波那契数（Fibonacci Number）是面试中最经典的入门动态规划题，其递推定义极其简洁：

$$ f(n + 1) = f(n) + f(n - 1) $$

即数列第 $n+1$ 项等于前两项之和，配合初始值 $f(0) = 0$、$f(1) = 1$，可逐项递推出完整数列：$0, 1, 1, 2, 3, 5, 8, 13, \dots$。

尽管题目本身简单，但它承载了算法面试中最重要的思想训练：同一个问题，用朴素递归、记忆化递归、动态规划三种思路实现，性能从指数级优化到线性级，空间从 $O(N)$ 压缩到 $O(1)$。这一"降维打击"的过程，正是动态规划思想的核心价值所在。在本仓库中，该题同时收录于 selected_coding_interview 与剑指 Offer 板块（剑指 Offer 10- I. 斐波那契数列），两处解法一脉相承，可对照阅读。

三种解法思路总览

生成第 $n$ 项斐波那契数，由简到繁主要有以下三种做法：

解法	核心原理	时间复杂度	空间复杂度	主要缺点
暴力搜索（朴素递归）	将 $f(n)$ 拆分为 $f(n-1)$ 与 $f(n-2)$ 两个子问题递归求解，以 $f(0)$、$f(1)$ 为终止条件	$O(2^n)$	$O(n)$（递归栈深度）	大量重复计算，指数级爆炸
记忆化递归	递归基础上新增数组缓存已算出的 $f(0) \sim f(n)$，重复子问题直接查表	$O(n)$	$O(n)$	需要额外 $O(N)$ 存储空间
动态规划	以 $f(n+1) = f(n) + f(n-1)$ 为转移方程自底向上迭代	$O(n)$	$O(n)$，可压缩至 $O(1)$	无（本题最佳解法）

从计算效率与空间复杂度两个维度综合衡量，动态规划（含状态压缩）是本题的最佳解法，也是面试中最推荐的实现方式。

暴力搜索：理解"重叠子问题"

暴力搜索的原理非常直观：把 $f(n)$ 问题的计算拆分成 $f(n-1)$ 和 $f(n-2)$ 两个子问题的计算，并不断递归，以 $f(0)$ 和 $f(1)$ 为终止条件。对应伪代码为：

fib(n): if n == 0: return 0 if n == 1: return 1 return fib(n-1) + fib(n-2)

缺点：大量重复的递归计算。例如 $f(n)$ 与 $f(n-1)$ 两者向下递归时，需要各自计算一次 $f(n-2)$ 的值；随着递归深度增加，$f(n-3)$、$f(n-4)$ 等子问题会被重复计算的次数呈指数级增长，整体时间复杂度退化到 $O(2^n)$。这种"子问题被重复求解"的现象，正是动态规划中著名的**重叠子问题（Overlapping Subproblems）**概念——它是判断一个问题能否用动态规划求解的两大特征之一。

记忆化递归：用空间换时间

记忆化递归（Memoization）在递归法的基础上，新建一个长度为 $n$ 的数组，用于在递归时存储 $f(0)$ 至 $f(n)$ 的数字值：

memo = [-1] * (n + 1) # 初始化缓存，-1 表示未计算 fib(n): if n == 0: return 0 if n == 1: return 1 if memo[n] != -1: return memo[n] # 重复遇到某数字直接从数组取用 memo[n] = fib(n-1) + fib(n-2) return memo[n]

其原理是：重复遇到某数字则直接从数组取用，避免了重复的递归计算，将时间复杂度从 $O(2^n)$ 降为 $O(n)$。缺点：记忆化存储需要使用 $O(N)$ 的额外空间。这里"以空间换时间"的取舍，是记忆化与后续动态规划的共同思想基础。

动态规划解析：四步法

动态规划把自顶向下的递归改写为自底向上的迭代，其标准四步为：状态定义 → 转移方程 → 初始状态 → 返回值。

状态定义：设 $dp$ 为一维数组，其中 $dp[i]$ 的值代表斐波那契数列第 $i$ 个数字；
转移方程：$dp[i + 1] = dp[i] + dp[i - 1]$，即对应数列定义 $f(n + 1) = f(n) + f(n - 1)$；
初始状态：$dp[0] = 0$，$dp[1] = 1$，即初始化前两个数字；
返回值：$dp[n]$，即斐波那契数列的第 $n$ 个数字。

对应伪代码为：

dp = [0] * (n + 1) dp[0], dp[1] = 0, 1 for i in range(2, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[n]

这一流程可以无缝迁移到几乎所有一维 DP 题：例如仓库中的 70. 爬楼梯（lc_70_climbing_stairs.py），其状态定义 $dp[i]$ 为爬到第 $i$ 阶的方法数，转移方程 $dp[i] = dp[i-1] + dp[i-2]$ 与本题几乎一致，只是初始状态改为 $dp[0] = dp[1] = 1$。掌握本题，等于拿到了通往一组"斐波那契系" DP 题的钥匙。

状态压缩：把 $O(N)$ 空间降到 $O(1)$

若新建长度为 $n$ 的 $dp$ 列表，则空间复杂度为 $O(N)$。

状态压缩的核心观察：由于 $dp$ 列表第 $i$ 项只与第 $i-1$ 和第 $i-2$ 项有关，前面的所有状态在计算出后续状态后便不再被使用。因此只需要初始化三个整型变量sum、a、b，利用辅助变量sum使 $a, b$ 两数字交替前进即可（具体实现见下文代码）。这一技巧在 DP 领域极为通用，几乎所有"只依赖前两个状态"的递推问题（爬楼梯、青蛙跳台阶、打家劫舍等）都可套用。

迭代过程中a始终代表 $f(i)$，b始终代表 $f(i+1)$；
每轮先计算sum = a + b得到下一项，再依次将a = b、b = sum，实现两个变量"滚动前进"；
循环结束后返回a，即为 $f(n)$。

节省了 $dp$ 列表空间，因此空间复杂度降至 $O(1)$。这也是 LeetCode-Book 在本题所有语言实现中统一采用的最终版本。

三语言代码实现（与仓库源码一致）

以下三份实现与仓库 selected_coding_interview/codes 目录下的实际源码完全一致，均为状态压缩后的 $O(1)$ 空间版本：

class Solution: def fib(self, n: int) -> int: a, b = 0, 1 for _ in range(n): a, b = b, a + b return a

对应仓库文件：lc_509_fibonacci_number.py。Python 的多元赋值a, b = b, a + b会先计算右侧的(b, a+b)再同时赋值，天然实现了sum辅助变量的作用，因此无需显式声明sum。

class Solution { public int fib(int n) { int a = 0, b = 1, sum; for(int i = 0; i < n; i++){ sum = a + b; a = b; b = sum; } return a; } }

对应仓库文件：lc_509_fibonacci_number.java。Java 需要显式引入sum临时变量完成滚动。

class Solution { public: int fib(int n) { int a = 0, b = 1, sum; for(int i = 0; i < n; i++){ sum = a + b; a = b; b = sum; } return a; } };

对应仓库文件：lc_509_fibonacci_number_s1.cpp。C++ 版本还附带了可独立运行的main()驱动代码：int n = 4; ... cout << slt->fib(n) << endl;，可直接编译运行验证输出。

三种语言的循环控制均为恰好执行 $n$ 次迭代：当 $n = 0$ 时循环体不执行，直接返回初始值a = 0，正确覆盖边界情况；当 $n = 1$ 时执行一次a, b = b, a + b后返回a = 1，同样正确。

从源码看仓库的代码组织约定

细读仓库源码可以发现 LeetCode-Book 在代码组织上的一致性约定：

每个题目文件以lc_前缀 + 题号 + 题名命名（Python 为单文件，Java/C++ 为按题号分目录），如本题的 lc_509_fibonacci_number.py；
文件头部统一记录创建时间与作者信息；
Python 版本通过from include import *引入仓库自建的 include 工具包（内含TreeNode、ListNode等数据结构工具类与print_matrix等打印工具），并预留Test Case与Driver Code区块便于本地运行调试。

大数越界问题与取模变体（延伸阅读）

LeetCode-Book 在剑指 Offer 板块收录了本题的取模变体——剑指 Offer 10- I. 斐波那契数列，要求答案对1000000007取模，可用于观察大数场景下的处理方式。

sfo_10i_fibonacci_numbers_s1.py：在每轮迭代内取模，a, b = b, (a + b) % 1000000007，全程保证数值不越界；
sfo_10i_fibonacci_numbers_s2.py：先不处理越界、最后统一return a % 1000000007，并注释说明"不考虑大数越界问题"。

对照学习这两份变体，可以直观理解"迭代中取模"与"结果取模"在数值安全性上的差异，这对 C++/Java 这类存在整型溢出的语言尤为重要。