斐波那契数列讲透动态规划：从递归到滚动数组的完整进阶

如果有人让我用一道题讲清楚动态规划，我会毫不犹豫地选斐波那契数列。原因很简单：这个看似简单到只有一行递推公式的问题，恰恰浓缩了动态规划最核心的三个要素——状态定义、状态转移方程和边界条件。国内很多算法教材把斐波那契当成"递归入门题"，说实话有点浪费，它应该是你建立算法思维的第一块跳板。这期专题，我就以斐波那契模型为引子，从数学递推讲到动态规划的核心思维方式，顺便把搜索、记忆化、滚动数组、矩阵快速幂这些相关的技术点一次性串起来。

这篇文章适合刚接触算法的学生、准备机试或面试的开发者，以及那些刷了几十道动态规划题但一直感觉"看懂答案、自己不会做"的朋友。我会用大量代码和推导过程，把每一步思考的逻辑讲透，而不是只丢给你一个结论。

1. 为什么选斐波那契数列当动态规划的第一课

1.1 一道"简单题"背后的三个关键特征

斐波那契数列的定义大家都很熟了：F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)。这个定义看起来只是一个数学公式，但如果你换个视角看它，会发现它具备动态规划问题需要的一切要素。

第一个特征：重叠子问题。计算F(5)需要F(4)和F(3)，计算F(4)又需要F(3)和F(2)。注意，F(3)在这里被重复计算了两次，F(2)被重复计算得更多。如果画出递归调用树，你会发现大部分节点都在做重复劳动。这就是"重叠子问题"——动态规划能优化时间的根本原因之一。

第二个特征：最优子结构。F(5)的最优解（也就是它的数值）可以由F(4)和F(3)的最优解直接推出来，子问题的最优解组合起来就是原问题的最优解。这是动态规划能成立的另一个前提。

第三个特征：状态转移方程明确。DP[N] = DP[N-1] + DP[N-2]，这就是状态转移方程。它描述的是"如何用更小的问题答案推出当前问题的答案"，是动态规划代码里最核心的那一行。

你把它和后面的背包问题、最长上升子序列对比一下就会发现，斐波那契只是状态转移方程长得最简单，但它的结构逻辑和其他DP问题没有本质区别。把这一题吃透，后面的路会顺很多。

1.2 递推公式本身就是状态转移方程

很多人学了动态规划后会产生一个错觉，觉得状态转移方程是某种高深莫测的东西。其实数学归纳法里的递推式，就是最早的"状态转移方程"。

我上课的时候经常问学生一个问题："如果题目把斐波那契数列的递推公式给你，你还会觉得这题难吗？"答案是不会。那动态规划难在哪？难在题目不给你递推公式，而让你自己从问题描述里"发现"这个递推关系。

斐波那契模型的价值，恰恰在于它是你见过的第一个"递推公式"，把它彻底搞懂，你就知道状态转移方程长什么样。以后见到"dp[i]表示什么""转移方程怎么列"这些问题时，你脑子里会有一个具体的参照物：哦，原来就是类似于斐波那契那样的关系式。

1.3 顺带回应一个热搜问题：KMP算法算不算动态规划

网上有个高频问题：KMP算法属于动态规划吗？借着斐波那契这个话题我多说一句。

KMP算法的核心是next数组（也叫前缀函数），求解next数组时确实用了"借助之前已经算好的信息来推导当前值"的思想——从这点看它和动态规划有点像。但严格来说，KMP的主算法属于字符串匹配算法，next数组计算可以理解为一种带有贪心回溯的递推，而不是典型意义上的动态规划。

为什么？因为动态规划要求把问题划分为重叠子问题，且子问题之间具备最优子结构；而KMP的next数组求解，虽然形式上是递推，但其本质是"模式串的前后缀匹配信息传递"，是有限状态自动机的思想。你可以用DP的视角去解释它、理解它，但不能说KMP就是动态规划算法。这个区分在面试中偶尔会被问到，提前理清楚，能省很多口舌。

2. 从递归到记忆化搜索：先能跑，再谈优化

2.1 朴素的递归为什么会指数爆炸

先看最直观的写法：

def fib_recursive(n): if n <= 1: return n return fib_recursive(n - 1) + fib_recursive(n - 2)

这段代码逻辑完全正确，但性能极其糟糕。n=40的时候，递归调用次数已经超过3亿次，肉眼可见地卡顿。原因是这个递归过程产生了大量重复计算。我画过递归调用树，n=6时F(4)会出现2次，F(3)出现3次，F(2)出现5次，F(1)出现8次——重复量是指数级的，整体时间复杂度高达O(2^n)。

新手最容易踩的坑是：以为"递归就是动态规划"。其实朴素递归只是暴力枚举的一种实现方式，它没有利用重叠子问题的性质，所以不能算动态规划。

2.2 加入一个memo数组，复杂度断崖式下降

优化的思路非常朴素：既然同一个子问题会被反复计算，那我算完一次就存起来，下次用到时直接查表，不再重复计算。这就是记忆化搜索（Memoization），也叫"带备忘录的递归"、自顶向下的动态规划。

def fib_memo(n, memo=None): if memo is None: memo = {0: 0, 1: 1} if n in memo: return memo[n] memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo) return memo[n]

加了一个字典（或者数组）后，每个子问题只会计算一次，时间复杂度从O(2^n)骤降到O(n)，空间复杂度O(n)。我之前实测过n=100的场景，不带备忘录的递归直接跑不出来，带备忘录的瞬间出结果。

这个反差能让你直观体会到"重复子问题"对性能的杀伤力。做任何动态规划题，先写出这个带缓存的递归版本，往往比直接硬凑循环更容易理清思路。

2.3 记忆化搜索的适用范围和边界

记忆化搜索并非万能。它的优势在于代码直观、与递归思维一致，不易写错；劣势在于递归有函数调用开销，而且当递归深度很大时可能爆栈。Python中默认递归深度限制是1000左右，n稍微大一点就会出现RecursionError。

所以我的经验是：面试或笔试中遇到动态规划题，如果一下子想不出迭代写法，先用记忆化搜索拿到正确结果，再考虑改写成循环。这个策略能帮你在一道DP题目上优先得分，后续再优化也不会丢思路。

3. 自底向上的真·动态规划：状态设计与循环写法

3.1 从递归的"倒着算"到迭代的"正着推"

记忆化搜索是自顶向下，从F(n)开始，一路递归到F(0)、F(1)，再返回值累加得到结果。而经典动态规划采用自底向上：先算出F(0)、F(1)，再逐步推到F(n)。代码长这样：

def fib_dp(n): if n <= 1: return 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数组就是"DP表"，dp[i]表示第i个斐波那契数。循环从2走到n，每一步都在执行状态转移方程dp[i] = dp[i-1] + dp[i-2]。

这种写法的好处是：无递归爆栈风险，执行效率高（Python的for循环比递归函数调用开销小很多）。它也是绝大多数动态规划题目代码的最终形态。

3.2 状态遍历顺序为什么是从小到大

你在很多题解里会看到"dp数组的遍历方向很重要"这样的提示。斐波那契的状态转移只依赖前两个状态，所以遍历顺序天然是从小到大递增。但这背后其实是一个更普遍的原则：在计算当前状态时，它所依赖的所有前置状态必须已经被计算出来。

拿爬楼梯问题来说，到达第i阶的方法数等于第i-1阶的方法数加第i-2阶的方法数（因为最后一步要么跨1级，要么跨2级）。这和斐波那契是完全一样的数学结构。你甚至可以直接套用斐波那契的dp代码，把初始化调整一下就通过。这就是模型的复用。

以后做到二维动态规划（比如01背包），遍历顺序为什么有时候要倒序、有时候要正序，本质上就是在回答"当前状态依赖的是上一行的旧值，还是本行已经更新的新值"。这个问题我们现在先埋个伏笔，等讲背包专题的时候再展开。

3.3 滚动数组与空间压缩的完整推导

很多教材讲斐波那契会提到"空间优化"，但只说"用三个变量就够了"，却不说为什么。我来完整推一推。

观察状态转移方程dp[i] = dp[i-1] + dp[i-2]，你会发现计算dp[i]时，只需要知道dp[i-1]和dp[i-2]，dp[i-3]及以前的信息根本用不上。那为什么还要开一个长度为n+1的数组？没必要。用两个变量滚动更新即可：

def fib_optimized(n): if n <= 1: return n prev2, prev1 = 0, 1 cur = 0 for _ in range(2, n + 1): cur = prev1 + prev2 prev2 = prev1 prev1 = cur return cur

变量prev2和prev1分别表示dp[i-2]和dp[i-1]，每计算完一个新值，就把它们整体"往前滚"一位。空间复杂度从O(n)降到O(1)，时间复杂度仍然是O(n)。

我见过不少人在这一步犯迷糊，尤其是循环里"先赋值再滚动"的顺序容易搞混。我的建议是：先在草稿纸上模拟n=5的整个过程，把每轮循环开始前prev1和prev2的值写出来，再对照代码走一遍。走一遍就再也忘不掉了。

这个"滚动数组"思想在后面很多动态规划问题里都会用到，尤其是空间限制严格的题目，或者2D转1D的优化场景。

4. 从斐波那契到动态规划建模思维

4.1 状态定义：一个下标就是一个决策节点

做动态规划题，第一步永远是问自己："我要用什么样的状态来刻画这个问题？"在斐波那契模型里，状态就是"当前是第几个数"，用一个整数下标i就可以表示。状态值dp[i]表示第i个数的大小。

到更复杂的题目里，状态可能有多个维度：背包问题需要"前i个物品+容量j"两个维度，所以dp[i][j]表示前i个物品放入容量为j的背包能获得的最大价值。但不管状态维度如何，核心思想都一样：用状态变量去描述问题在某个阶段的情况。

这里我给新手一个实用技巧：当你不知道怎么定义状态时，先看问题问的是什么。问"第n项是多少"，状态就是"第i项的值"；问"前i个物品能装多少",状态就是"前i个物品的容量"；问"到第i个位置的最长长度"，状态就是"以第i个位置结尾的长度"。状态定义通常和题目问法高度相关。

4.2 状态转移方程：把大问题拆成小问题的"连接件"

状态转移方程是整个动态规划的灵魂。它的本质是："当前状态可以由哪几个更小的状态，通过什么运算得到？"

以斐波那契为例：dp[i] = dp[i-1] + dp[i-2]，意思就是第i个数等于它前面两个数相加。这条方程很直白，但它背后蕴含的思维方式是：把一个规模为i的问题，拆成两个规模为i-1和i-2的子问题。

如果你只看"加法"这一步，会觉得简单；但到了爬楼梯、打家劫舍、斐波那契变形题里，"转移"的形式会变，比如变成"要么走1步、要么走2步，所以方法数相加"，或者变成"要么偷当前这家、要么不偷，取最大值"。形式变了，但逻辑框架不变。

我建议读者把斐波那契的转移方程背下来，不是为了背代码，而是为了建立一种条件反射：所有一维动态规划问题，解题时都优先想"dp[i]是从哪个dp[j]推过来的"。

4.3 初始化与边界条件：最容易翻车的环节

很多题目你能写出正确的状态定义和状态转移方程，但结果就是不对，大概率是初始化或边界条件出了问题。

斐波那契的初始条件是dp[0]=0、dp[1]=1。看起来简单，但有一个很经典的坑：当n=0或n=1时，有些人的循环里直接访问dp[2]，导致数组越界。所以我在代码里一开始就加了if n <= 1: return n的判空气语句。

到后面的动态规划题，初始化往往更讲究。比如打家劫舍问题，dp数组初始化为0，dp[0] = nums[0]（如果只有一家，那就偷这家），这就是边界条件。再比如最长上升子序列，每个位置的初始长度至少是1，因为单个元素也算一个递增子序列。

我的经验是：每次写完DP代码，先把n等于0、1、2这三个极小值代进去跑一遍。这三个值几乎能把90%的初始化问题暴露出来。

4.4 三个经典变形：爬楼梯、打家劫舍、矩阵快速幂

斐波那契模型为什么重要？因为有一大堆题都是它的马甲。最常见的三个：

爬楼梯。每次可以爬1级或2级台阶，爬到第n级有多少种方法？定义dp[i]为到达第i级台阶的方法数，那么最后一步要么从i-1上来，要么从i-2上来，所以dp[i] = dp[i-1] + dp[i-2]，初始化dp[1]=1，dp[2]=2。这就是斐波那契数列从第1项开始的版本。

打家劫舍。一排房子，每间有一定金额，不能偷相邻的，求能偷到的最大金额。定义dp[i]为前i间房子能偷到的最多金额，转移为dp[i] = max(dp[i-1], dp[i-2] + nums[i])。这个方程和斐波那契不再一样，但结构上仍然是"只看前两个状态"，仍然可以用滚动数组优化空间。

矩阵快速幂。如果需要计算F(10^18)，O(n)也不够看，这时候可以用矩阵乘法和快速幂把复杂度降到O(log n)。斐波那契的矩阵形式是：

[ F(n+1) ] = [1 1] ^ n [ F(1) ] [ F(n) ] [1 0] [ F(0) ]

利用矩阵的快速幂，可以在超大n的情况下也能很快求出答案。这属于进阶内容，但在算法竞赛和面试中偶尔会出现，值得了解。

我按难度从低到高排个对照表，方便你快速定位：

4.5 动态规划建模的核心方法论

从斐波那契这个例子，可以总结出动态规划建模的四步法，这个方法论在后面所有DP题目中通用：

第一步，明确状态。搞清楚问题到了哪个阶段、有哪些关键变量，用这些变量去定义dp数组的含义。

第二步，找状态转移。思考"最后一步怎么走"或者"当前状态由哪些前置状态决定"，列出转移方程。

第三步，设置边界。初始化dp的起始值，想清楚循环的起点和终点。

第四步，确认遍历顺序。根据转移方程依赖的方向，决定从小到大还是从大到小迭代，以及是否需要额外维度来存储中间结果。

拿斐波那契题练手时，这四步可能觉得有点"杀鸡用牛刀"，但一旦遇到真正复杂的DP题目，这个流程就是救命稻草。我见过太多人卡在"面对题目不知道从哪下手"，其实不是智商问题，而是缺少这套系统化的建模流程。

5. 常见问题与排查技巧实录

5.1 递归超时是不是就代表不能用递归

不是。递归超时是因为没有做"记忆化"，也就是没有缓存子问题的结果。做了记忆化后，递归版本的复杂度也是O(n)，只是常数项稍大一些。真正需要担心的是递归深度——Python默认递归深度限制大约1000，如果n很大，即使加了缓存也会报RecursionError。

我之前帮一个学生调代码，他用记忆化递归写了一个n=2000的题，本地跑得好好的（因为他的环境里递归深度被改大了），提交到平台就栈溢出。这种情况的直接解法是改写成迭代。所以在写记忆化搜索时，最好心里有个数：递归深度安全线在几百到几千之间，超出就换写法。

5.2 空间优化后代码看不懂了怎么办

很多人把prev2、prev1滚动数组写完后，隔几天再回头看，完全不记得每行代码在做什么。这个问题的根源是：滚动数组丢失了"语义信息"——dp[i]的"i"不见了，只剩下两个无名变量。

我的建议是两种方案择一：

方案一：在代码里写清楚注释，标注"prev2表示dp[i-2]，prev1表示dp[i-1]"。

方案二：先用完整dp数组写一遍，保证逻辑清晰、能通过测试，AC之后再改写成滚动数组版本。这个过程其实只花一两分钟，但能让你同时对两种写法都有把握。

我自己刷题时几乎都这么做：先写完整版，再压缩空间。面试时如果面试官要求"能不能优化空间"，我直接把压缩版写出来，而且能解释每一步，因为他看到的是我思考的过程，而不只是背下来的模板。

5.3 一维问题搞明白后，怎么过渡到二维DP

斐波那契模型是一维DP，很多读者会问："我接下来是不是可以直接挑战二维DP了？"我的建议是：不要急。

二维DP典型问题是"路径计数"、"网格路径最小和"、"最长公共子序列"等。它们的状态定义多了一个维度，转移方程也更复杂，但核心仍然是那四步。

以"不同路径"为例：一个m×n的网格，从左上角走到右下角，每次只能向右或向下走，问有多少条不同路径。定义dp[i][j]为到达(i,j)位置的方法数，那么dp[i][j] = dp[i-1][j] + dp[i][j-1]，就是"从上方下来"和"从左方过来"两种方式之和。加上边界条件dp[0][j]=1、dp[i][0]=1（因为第一行和第一列只能一直向右或一直向下走），这道题就解出来了。

你会看到，这个转移方程的思想和斐波那契几乎一模一样，只是把一个维度扩展成了两个维度而已。所以斐波那契模型练得好，二维DP的入门也不会太痛苦。

5.4 调试DP代码的几个辅助手段

DP代码跑出错来，最难的是定位。我常用的三招：

第一招，打印dp表。在循环里把每次算出来的dp值打出来，和手工推导的结果对一下，看哪一步开始不一致。对于斐波那契这类题目，你可能觉得没必要打印，但当n=6时把dp数组打印出来，能看到[0, 1, 1, 2, 3, 5, 8]这个序列，对新手建立"状态表"的概念非常有帮助。

第二招，用极小的用例自测。拿n=0、1、2、3、4这几个输入分别跑一遍，对比预期结果。这样做成本极低，但能快速发现问题。

第三招，看循环边界。很多DP出现结果的偏差，源头是range(2, n+1)这类边界条件写错。比如有人写成range(2, n)，那dp[n]就永远没被算出来，最后return dp[n]会越界或返回初始值。这是我见过最多的一类错误。

这三招下来，绝大多数DP问题都能定位到出错的位置。

写在最后的建议

斐波那契模型是整个动态规划专题的地基，你在这一题上花的时间不会白费。很多人会觉得这个题太简单，急着去刷难题，结果越刷越挫败。根据我自己带新人的经验，把斐波那契这道题用四种写法（朴素递归、记忆化搜索、DP数组、滚动数组）都实现一遍，再去做几道变形题，效果比盲目刷题要好得多。

另外，我强烈建议你在本地建一个专门的"动态规划题解模板"文件夹，每一题都按照"状态定义--转移方程--边界条件--遍历顺序--代码实现--复杂度分析"六个部分来记录。时间长了，你会发现自己对DP的直觉越来越准。

下一期专题，我打算聊聊"线性DP"的经典模型，比如最长上升子序列、最大子段和、编辑距离这些，它们都是在斐波那契模型的基础上扩展出来的。先把这一篇的代码和思路吃透，下期见。