如果有人让我用一道题讲清楚动态规划我会毫不犹豫地选斐波那契数列。原因很简单这个看似简单到只有一行递推公式的问题恰恰浓缩了动态规划最核心的三个要素——状态定义、状态转移方程和边界条件。国内很多算法教材把斐波那契当成递归入门题说实话有点浪费它应该是你建立算法思维的第一块跳板。这期专题我就以斐波那契模型为引子从数学递推讲到动态规划的核心思维方式顺便把搜索、记忆化、滚动数组、矩阵快速幂这些相关的技术点一次性串起来。这篇文章适合刚接触算法的学生、准备机试或面试的开发者以及那些刷了几十道动态规划题但一直感觉看懂答案、自己不会做的朋友。我会用大量代码和推导过程把每一步思考的逻辑讲透而不是只丢给你一个结论。1. 为什么选斐波那契数列当动态规划的第一课1.1 一道简单题背后的三个关键特征斐波那契数列的定义大家都很熟了F(0)0F(1)1F(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)这段代码逻辑完全正确但性能极其糟糕。n40的时候递归调用次数已经超过3亿次肉眼可见地卡顿。原因是这个递归过程产生了大量重复计算。我画过递归调用树n6时F(4)会出现2次F(3)出现3次F(2)出现5次F(1)出现8次——重复量是指数级的整体时间复杂度高达O(2^n)。新手最容易踩的坑是以为递归就是动态规划。其实朴素递归只是暴力枚举的一种实现方式它没有利用重叠子问题的性质所以不能算动态规划。2.2 加入一个memo数组复杂度断崖式下降优化的思路非常朴素既然同一个子问题会被反复计算那我算完一次就存起来下次用到时直接查表不再重复计算。这就是记忆化搜索Memoization也叫带备忘录的递归、自顶向下的动态规划。def fib_memo(n, memoNone): 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)。我之前实测过n100的场景不带备忘录的递归直接跑不出来带备忘录的瞬间出结果。这个反差能让你直观体会到重复子问题对性能的杀伤力。做任何动态规划题先写出这个带缓存的递归版本往往比直接硬凑循环更容易理清思路。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]及以前的信息根本用不上。那为什么还要开一个长度为n1的数组没必要。用两个变量滚动更新即可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)。我见过不少人在这一步犯迷糊尤其是循环里先赋值再滚动的顺序容易搞混。我的建议是先在草稿纸上模拟n5的整个过程把每轮循环开始前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。看起来简单但有一个很经典的坑当n0或n1时有些人的循环里直接访问dp[2]导致数组越界。所以我在代码里一开始就加了if n 1: return n的判空气语句。到后面的动态规划题初始化往往更讲究。比如打家劫舍问题dp数组初始化为0dp[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]1dp[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(n1) ] [1 1] ^ n [ F(1) ] [ F(n) ] [1 0] [ F(0) ]利用矩阵的快速幂可以在超大n的情况下也能很快求出答案。这属于进阶内容但在算法竞赛和面试中偶尔会出现值得了解。我按难度从低到高排个对照表方便你快速定位题目变体状态定义状态转移难度斐波那契数列dp[i]第i个数dp[i]dp[i-1]dp[i-2]入门爬楼梯dp[i]到第i级的方法数dp[i]dp[i-1]dp[i-2]入门打家劫舍dp[i]前i间房的最大金额dp[i]max(dp[i-1], dp[i-2]nums[i])简单矩阵快速幂求斐波那契矩阵幂F(n)矩阵乘法结果进阶4.5 动态规划建模的核心方法论从斐波那契这个例子可以总结出动态规划建模的四步法这个方法论在后面所有DP题目中通用第一步明确状态。搞清楚问题到了哪个阶段、有哪些关键变量用这些变量去定义dp数组的含义。第二步找状态转移。思考最后一步怎么走或者当前状态由哪些前置状态决定列出转移方程。第三步设置边界。初始化dp的起始值想清楚循环的起点和终点。第四步确认遍历顺序。根据转移方程依赖的方向决定从小到大还是从大到小迭代以及是否需要额外维度来存储中间结果。拿斐波那契题练手时这四步可能觉得有点杀鸡用牛刀但一旦遇到真正复杂的DP题目这个流程就是救命稻草。我见过太多人卡在面对题目不知道从哪下手其实不是智商问题而是缺少这套系统化的建模流程。5. 常见问题与排查技巧实录5.1 递归超时是不是就代表不能用递归不是。递归超时是因为没有做记忆化也就是没有缓存子问题的结果。做了记忆化后递归版本的复杂度也是O(n)只是常数项稍大一些。真正需要担心的是递归深度——Python默认递归深度限制大约1000如果n很大即使加了缓存也会报RecursionError。我之前帮一个学生调代码他用记忆化递归写了一个n2000的题本地跑得好好的因为他的环境里递归深度被改大了提交到平台就栈溢出。这种情况的直接解法是改写成迭代。所以在写记忆化搜索时最好心里有个数递归深度安全线在几百到几千之间超出就换写法。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值打出来和手工推导的结果对一下看哪一步开始不一致。对于斐波那契这类题目你可能觉得没必要打印但当n6时把dp数组打印出来能看到[0, 1, 1, 2, 3, 5, 8]这个序列对新手建立状态表的概念非常有帮助。第二招用极小的用例自测。拿n0、1、2、3、4这几个输入分别跑一遍对比预期结果。这样做成本极低但能快速发现问题。第三招看循环边界。很多DP出现结果的偏差源头是range(2, n1)这类边界条件写错。比如有人写成range(2, n)那dp[n]就永远没被算出来最后return dp[n]会越界或返回初始值。这是我见过最多的一类错误。这三招下来绝大多数DP问题都能定位到出错的位置。写在最后的建议斐波那契模型是整个动态规划专题的地基你在这一题上花的时间不会白费。很多人会觉得这个题太简单急着去刷难题结果越刷越挫败。根据我自己带新人的经验把斐波那契这道题用四种写法朴素递归、记忆化搜索、DP数组、滚动数组都实现一遍再去做几道变形题效果比盲目刷题要好得多。另外我强烈建议你在本地建一个专门的动态规划题解模板文件夹每一题都按照状态定义--转移方程--边界条件--遍历顺序--代码实现--复杂度分析六个部分来记录。时间长了你会发现自己对DP的直觉越来越准。下一期专题我打算聊聊线性DP的经典模型比如最长上升子序列、最大子段和、编辑距离这些它们都是在斐波那契模型的基础上扩展出来的。先把这一篇的代码和思路吃透下期见。
斐波那契数列讲透动态规划：从递归到滚动数组的完整进阶
如果有人让我用一道题讲清楚动态规划我会毫不犹豫地选斐波那契数列。原因很简单这个看似简单到只有一行递推公式的问题恰恰浓缩了动态规划最核心的三个要素——状态定义、状态转移方程和边界条件。国内很多算法教材把斐波那契当成递归入门题说实话有点浪费它应该是你建立算法思维的第一块跳板。这期专题我就以斐波那契模型为引子从数学递推讲到动态规划的核心思维方式顺便把搜索、记忆化、滚动数组、矩阵快速幂这些相关的技术点一次性串起来。这篇文章适合刚接触算法的学生、准备机试或面试的开发者以及那些刷了几十道动态规划题但一直感觉看懂答案、自己不会做的朋友。我会用大量代码和推导过程把每一步思考的逻辑讲透而不是只丢给你一个结论。1. 为什么选斐波那契数列当动态规划的第一课1.1 一道简单题背后的三个关键特征斐波那契数列的定义大家都很熟了F(0)0F(1)1F(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)这段代码逻辑完全正确但性能极其糟糕。n40的时候递归调用次数已经超过3亿次肉眼可见地卡顿。原因是这个递归过程产生了大量重复计算。我画过递归调用树n6时F(4)会出现2次F(3)出现3次F(2)出现5次F(1)出现8次——重复量是指数级的整体时间复杂度高达O(2^n)。新手最容易踩的坑是以为递归就是动态规划。其实朴素递归只是暴力枚举的一种实现方式它没有利用重叠子问题的性质所以不能算动态规划。2.2 加入一个memo数组复杂度断崖式下降优化的思路非常朴素既然同一个子问题会被反复计算那我算完一次就存起来下次用到时直接查表不再重复计算。这就是记忆化搜索Memoization也叫带备忘录的递归、自顶向下的动态规划。def fib_memo(n, memoNone): 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)。我之前实测过n100的场景不带备忘录的递归直接跑不出来带备忘录的瞬间出结果。这个反差能让你直观体会到重复子问题对性能的杀伤力。做任何动态规划题先写出这个带缓存的递归版本往往比直接硬凑循环更容易理清思路。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]及以前的信息根本用不上。那为什么还要开一个长度为n1的数组没必要。用两个变量滚动更新即可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)。我见过不少人在这一步犯迷糊尤其是循环里先赋值再滚动的顺序容易搞混。我的建议是先在草稿纸上模拟n5的整个过程把每轮循环开始前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。看起来简单但有一个很经典的坑当n0或n1时有些人的循环里直接访问dp[2]导致数组越界。所以我在代码里一开始就加了if n 1: return n的判空气语句。到后面的动态规划题初始化往往更讲究。比如打家劫舍问题dp数组初始化为0dp[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]1dp[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(n1) ] [1 1] ^ n [ F(1) ] [ F(n) ] [1 0] [ F(0) ]利用矩阵的快速幂可以在超大n的情况下也能很快求出答案。这属于进阶内容但在算法竞赛和面试中偶尔会出现值得了解。我按难度从低到高排个对照表方便你快速定位题目变体状态定义状态转移难度斐波那契数列dp[i]第i个数dp[i]dp[i-1]dp[i-2]入门爬楼梯dp[i]到第i级的方法数dp[i]dp[i-1]dp[i-2]入门打家劫舍dp[i]前i间房的最大金额dp[i]max(dp[i-1], dp[i-2]nums[i])简单矩阵快速幂求斐波那契矩阵幂F(n)矩阵乘法结果进阶4.5 动态规划建模的核心方法论从斐波那契这个例子可以总结出动态规划建模的四步法这个方法论在后面所有DP题目中通用第一步明确状态。搞清楚问题到了哪个阶段、有哪些关键变量用这些变量去定义dp数组的含义。第二步找状态转移。思考最后一步怎么走或者当前状态由哪些前置状态决定列出转移方程。第三步设置边界。初始化dp的起始值想清楚循环的起点和终点。第四步确认遍历顺序。根据转移方程依赖的方向决定从小到大还是从大到小迭代以及是否需要额外维度来存储中间结果。拿斐波那契题练手时这四步可能觉得有点杀鸡用牛刀但一旦遇到真正复杂的DP题目这个流程就是救命稻草。我见过太多人卡在面对题目不知道从哪下手其实不是智商问题而是缺少这套系统化的建模流程。5. 常见问题与排查技巧实录5.1 递归超时是不是就代表不能用递归不是。递归超时是因为没有做记忆化也就是没有缓存子问题的结果。做了记忆化后递归版本的复杂度也是O(n)只是常数项稍大一些。真正需要担心的是递归深度——Python默认递归深度限制大约1000如果n很大即使加了缓存也会报RecursionError。我之前帮一个学生调代码他用记忆化递归写了一个n2000的题本地跑得好好的因为他的环境里递归深度被改大了提交到平台就栈溢出。这种情况的直接解法是改写成迭代。所以在写记忆化搜索时最好心里有个数递归深度安全线在几百到几千之间超出就换写法。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值打出来和手工推导的结果对一下看哪一步开始不一致。对于斐波那契这类题目你可能觉得没必要打印但当n6时把dp数组打印出来能看到[0, 1, 1, 2, 3, 5, 8]这个序列对新手建立状态表的概念非常有帮助。第二招用极小的用例自测。拿n0、1、2、3、4这几个输入分别跑一遍对比预期结果。这样做成本极低但能快速发现问题。第三招看循环边界。很多DP出现结果的偏差源头是range(2, n1)这类边界条件写错。比如有人写成range(2, n)那dp[n]就永远没被算出来最后return dp[n]会越界或返回初始值。这是我见过最多的一类错误。这三招下来绝大多数DP问题都能定位到出错的位置。写在最后的建议斐波那契模型是整个动态规划专题的地基你在这一题上花的时间不会白费。很多人会觉得这个题太简单急着去刷难题结果越刷越挫败。根据我自己带新人的经验把斐波那契这道题用四种写法朴素递归、记忆化搜索、DP数组、滚动数组都实现一遍再去做几道变形题效果比盲目刷题要好得多。另外我强烈建议你在本地建一个专门的动态规划题解模板文件夹每一题都按照状态定义--转移方程--边界条件--遍历顺序--代码实现--复杂度分析六个部分来记录。时间长了你会发现自己对DP的直觉越来越准。下一期专题我打算聊聊线性DP的经典模型比如最长上升子序列、最大子段和、编辑距离这些它们都是在斐波那契模型的基础上扩展出来的。先把这一篇的代码和思路吃透下期见。