我见过太多人学动态规划第一反应就是去背状态转移方程。结果呢换个题目就不会了。背了dp[i] dp[i-1] dp[i-2]遇到爬楼梯、不同路径、解码方法照样两眼一抹黑。这事我以前也干过直到我重新把斐波那契数列模型彻底啃透才明白动态规划到底在干什么。斐波那契数列是什么F(0)0F(1)1F(n)F(n-1)F(n-2)。这是小学奥数就教过的数学递推。但它一旦放进算法的语境里就成了动态规划最标准的入门模型。数学递推解决的是“已知前两项求后一项”算法思维解决的是“怎么算最省时间、最省空间、最不容易出错”。这一篇文章我从斐波那契这个点切入讲清楚动态规划最核心的几条逻辑链路状态怎么定义、转移方程怎么列、遍历顺序怎么定、空间优化怎么做。不堆公式用你能直接跑的代码和能复现的思路来讲适合刚接触DP的算法初学者也适合那些背了很多方程但始终没打通任督二脉的选手。1. 从一道“会做的题”开始你真的懂斐波那契吗先别翻代码。我问你三个问题你能立刻答上来说明你确实懂了答不上来这篇文章你该仔细看看。问题一朴素递归求F(40)大概需要多少次函数调用问题二为什么dp数组的遍历顺序是0→n而不是n→0问题三为什么滚动数组只用两个变量就够了三个行不行四个行不行这三个问题分别对应重叠子问题、遍历顺序、空间优化。恰好就是动态规划三板斧。教科书上定义斐波那契数列只是给了个数学递推式F(0) 0 F(1) 1 F(n) F(n-1) F(n-2)n ≥ 2这个式子本身没有任何算法含量。它只说了一件事这一项由前两项决定。但你真拿它写递归会发现程序慢得像蜗牛。为什么看代码def fib(n): if n 1: return n return fib(n-1) fib(n-2)这段代码逻辑完全正确但效率极低。F(40)约需1.6亿次函数调用F(50)就要超过200亿次等到花儿都谢了。问题出在哪重复计算。你算F(40)的时候F(38)被算了三次F(35)被算了不知道多少次。这些重复计算白白浪费了CPU但斐波那契的递推结构恰好把这些重复暴露得明明白白这就是“重叠子问题”。动态规划解决的根本问题就是避免重复计算把已经算过的结果存起来下次直接用。2. 四种写法四个层次从递归到滚动数组斐波那契数列的实现几乎是学习DP实现演进的绝佳素材。我给新手上课时从来不讲什么高深理论就让他们把同一条题目用四种方法写出来写完自然就通了大半。2.1 朴素递归数学式子的最直接翻译最直观的写法就是上面那段Python代码纯粹把数学递推式翻译成代码。优点好写好理解。缺点慢到怀疑人生。复杂度分析一下T(n) T(n-1) T(n-2) O(1)展开后 T(n) O(2^n)。指数级复杂度n稍微大一点就彻底废了。这里需要留意的是这不是代码质量问题而是算法结构问题。哪怕换成C、Java只要结构是递归重复计算复杂度就不会变。很多人以为换个语言就能变快其实根本没抓住要害。2.2 记忆化搜索把重复计算缓存起来既然重复计算是元凶那我把每算过的结果存进字典或数组下次需要直接取不就行了吗def fib_memo(n): memo {0: 0, 1: 1} def helper(k): if k in memo: return memo[k] memo[k] helper(k-1) helper(k-2) return memo[k] return helper(n)这就是记忆化搜索也叫自顶向下的动态规划。递归入口是求F(n)然后向下拆到F(n-1)、F(n-2)直到基准情形。一旦某个子问题算过就存进memo后续直接读。复杂度立刻降到O(n)每个状态只算一次。但这里有一个极其重要的思维转变**memo里存的是什么是子问题的解。**这一步其实就是“状态”概念的雏形。memo[k]代表的就是第k个状态的值对应动态规划里“状态”这个词的含义。2.3 循环递推真正意义的动态规划递归记忆化虽然复杂度达标但递归本身有栈溢出风险而且会引入额外函数调用开销。更符合DP原教旨的做法是自底向上的循环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数组每个位置的值就是对应状态的最优解这个例子中没有“最优”单纯是解。为什么遍历顺序是从0到n因为状态转移的方向是向前依赖——要求dp[i]必须先有dp[i-1]和dp[i-2]。如果倒着遍历你算dp[n]时dp[n-1]和dp[n-2]还是未知的程序直接报错。这个道理看似简单却是DP遍历顺序问题的核心逻辑。2.4 滚动数组空间优化不是炫技观察递推式dp[i]只依赖dp[i-1]和dp[i-2]更早的状态用完之后再也用不到了。那何必开一整条数组用两个变量滚动覆盖就好。def fib_roll(n): if n 1: return n prev2, prev1 0, 1 for i in range(2, n 1): cur prev1 prev2 prev2, prev1 prev1, cur return prev1空间复杂度从O(n)降为O(1)。别小看这一步优化——后续很多DP题状态数组的规模直接从二维压到一维、从一维压到常数靠的就是滚动思想。比如背包问题里的空间优化本质上就是滚动数组的变体。这里需要强调空间优化的前提是状态转移只依赖相邻的几个状态。如果跳着依赖比如dp[i]依赖dp[i-3]那就得保留三个变量如果依赖全部历史状态那无法用滚动优化。每次动笔优化前先看转移方程依赖了哪些项。3. 斐波那契模型的核心状态定义是建模的第一步看懂了代码只是第一步。真正的分水岭在于如何从斐波那契数列抽象出一个通用的DP模型。很多初学者有个困惑为什么爬楼梯这道题是斐波那契题目是这样的每次可以爬1级或2级台阶问爬到第n级有多少种不同方法。设dp[i]为爬到第i级的方法数。到达第i级的方法要么从第i-1级直接上来要么从第i-2级跨两级上来。因此dp[i] dp[i-1] dp[i-2]这个式子和斐波那契一模一样。但注意问题语义完全不同斐波那契数列里F(n)就是数列的第n项爬楼梯里dp[i]代表的是“方法数”。同样的转移方程、不同的状态含义这就是模型迁移的本质。3.1 一个容易被忽略的问题递推方向由谁决定状态定义清楚之后递推方向不是拍脑袋定的而是由依赖关系决定的。原则只有一条计算当前状态所需的所有前置状态必须在之前已经算好。爬楼梯问题里dp[i]依赖dp[i-1]和dp[i-2]所以i从小到大遍历没问题。但有些题就需要反向遍历。比如后面学到背包问题dp[j] max(dp[j], dp[j-w[i]] v[i])如果正向遍历同一个物品会被重复放入多次那就变成完全背包了。所以01背包必须内层循环倒序遍历。这不是什么奇技淫巧而是严格由转移方程里状态依赖的方向决定的。斐波那契模型之所以适合入门正因为它的依赖方向简单直观——永远朝前看。你要借助这个简单场景把“由转移方程确定遍历顺序”这条方法论练成条件反射。3.2 模型迁移一爬楼梯代码实现时只需要微调边界条件。爬楼梯的问题里dp[0]通常设为1表示在第0级“一步不动”也算一种方案dp[1]1代表一步到第1级。def climb_stairs(n): if n 1: return 1 prev2, prev1 1, 1 for i in range(2, n 1): cur prev1 prev2 prev2, prev1 prev1, cur return prev1边界条件有讲究斐波那契数列从0开始F(0)0爬楼梯从1开始dp[0]1、dp[1]1最后返回dp[n]。边界值不同是因为两个问题的语义不同。不要拿到题就生搬硬套F(0)0那套先想清楚“下标为0代表什么”。3.3 模型迁移二不同路径LeetCode 62题机器人从m×n网格左上角走到右下角每次只能向下或向右问有多少条不同路径。设dp[i][j]为到达(i,j)的路径数。机器人只能从上方或左方过来所以dp[i][j] dp[i-1][j] dp[i][j-1]你仔细看这还是一维斐波那契的二维推广。每一格的转移只依赖相邻两格本质上还是“前两项求和”的思想只是从一维扩展到了二维。def unique_paths_with_obstacles(m, n): dp [[0] * n for _ in range(m)] dp[0][0] 1 if not obstacles[0][0] else 0 for i in range(m): for j in range(n): if not obstacles[i][j]: if i 0: dp[i][j] dp[i-1][j] if j 0: dp[i][j] dp[i][j-1] return dp[m-1][n-1]代码里的边界判断值得细品i0时加上方j0时加左方这样第0行和第0列就不用单独写初始化逻辑了。这个写法在DP题里非常常用能省掉一堆特殊情况的判断。3.4 模型迁移三解码方法LeetCode 91题“123”可以解码为“ABC”1,2,3或“LC”12,3问共有多少种解码方式。设dp[i]表示字符串前i个字符的解码方法数。第i个字符可以单独解码也可以和前一个字符合并解码单独解码要求字符在1~9之间此时dp[i] dp[i-1]合并解码要求前两个字符组成的数字在10~26之间此时dp[i] dp[i-2]def num_decodings(s): if not s or s[0] 0: return 0 n len(s) dp [0] * (n 1) dp[0], dp[1] 1, 1 for i in range(2, n 1): one int(s[i-1]) two int(s[i-2:i]) if 1 one 9: dp[i] dp[i-1] if 10 two 26: dp[i] dp[i-2] return dp[n]这道题比前两个例子高一个梯度因为它多了“条件转移”——不是所有情况下都能从上一个状态转移过来。但底层结构依然没脱出斐波那契模型的框架每个状态最多依赖前两个状态转移条件变了骨架还在。4. 从斐波那契看动态规划的三个基本性质斐波那契模型的价值远不止会做几道题。它把动态规划的三大性质展示得清清楚楚你在这个模型里感知到的每一条性质都能迁移到所有DP题目里。4.1 最优子结构大问题由小问题组合“最优子结构”这个术语很容易吓到新手。通俗解释大问题的最优解可以由子问题的最优解组合出来。斐波那契例子中F(5)的最优解就是它的值由F(4)F(3)构成而F(4)、F(3)本身又由更小的子问题构成。不存在说“为了求F(5)我得让F(4)取一个非最优值”。爬楼梯、最短路径、背包问题全都满足这个性质。判断一道题能不能用DP第一个问题就要问大问题和子问题之间是否存在这种“组合”关系比如求到第i级台阶的方法数能不能由到第i-1级和i-2级的方法数组合出来能那就DP不能想别的路子。4.2 无后效性过去不影响未来这是最抽象的一条也是初学者最容易绕晕的一条。无后效性的意思是某个状态一旦确定之后的状态只关心这个状态的值不关心它是怎么来的。斐波那契数列里F(5)等于多少只需要F(4)和F(3)的值至于F(4)是通过递归算出来的还是滚动数组算出来的根本不重要。历史路径完全不影响未来结果。这个性质决定了DP可以“无记忆地”递推。如果一道题里到达某个状态时你还需要知道“之前是怎么走的”那它就不是标准DP能解决的问题通常需要对状态进行扩充。比如状态不只存值还要存路径信息。无后效性是DP的护城河过不了这一关就不能用DP公式硬套。4.3 重叠子问题重复计算是优化的机会斐波那契的朴素递归慢慢在一模一样的子问题反复算。而DP的核心对策就是缓存子问题的解。判断一道题能否用DP第二个问题是否存在重叠子问题如果子问题完全不重叠那记忆化没有意义直接递归或分治就行。比如归并排序左右子数组排序相互独立没有重叠就不需要DP的缓存机制。斐波那契恰好把“重叠”这个概念具象化——画一棵递归树你肉眼可见F(38)被重复计算了好几次。在更复杂的题里这种重叠通常看不见要靠你分析转移方程时自己判断。5. 实操中的常见坑与排查技巧写DP题尤其在竞赛或者面试现场踩坑几乎是必经之路。这里分享几个我从斐波那契模型上遇到的问题和排查思路基本每一条在后续更复杂的DP题里都会遇到。5.1 状态定义不清晰我见过有同学写爬楼梯调了半天不对最后发现是dp数组的定义出了问题——他把dp[i]定义成“到第i级需要走的最小步数”但题目问的是“不同方案数”。定义错了转移方程全错代码怎么改都别扭。状态定义是DP的地基必须在动手前确认。我自己的习惯写注释把dp[i]的语义先写出来。比如# dp[i]: 到第i级台阶的爬法数量先把这句注释写好再写代码。表面上花十秒钟实际上能省掉后面十分钟的调试。做题多了你才会发现DP题百分之八十的难点在定义状态一旦定义对了转移方程往往水到渠成。5.2 溢出问题斐波那契数列增长极快F(50)约125亿F(100)约3.5e20。用C的intn超过46就溢出了。Python虽然有大整数不担心但换成其他语言很容易踩坑。解题时先估算下n的取值范围再决定用int还是long long必要时模一个大数如1e97。这也是很多题目明说“结果对10^97取模”的原因。否则你本地跑小数据都正确一旦提交大数据直接WA或者出现负数多半就是溢出。5.3 空间优化过早绕过误区不是所有题都该一上来就优化空间。很多新手看了滚动数组的写法觉得高端于是所有题都压缩成两个变量。结果状态定义改了以后需要保留一整条数组又把自己绕晕了。我的建议第一版代码先写完整的dp数组保证逻辑正确确认无误后再看转移方程依赖哪些状态决定能不能滚动。先对再优优化永远排在正确性之后。还有一点在回溯时通常需要保留全部状态不能滚动。比如要找具体路径而不是只求数量你压缩了数组就等于丢掉了历史信息。空间优化前先问自己后面要不要回溯。5.4 KMP到底是不是动态规划这是网络上经常被问到的问题。KMP算法里next数组的构建有递推关系例如在失配时next[j]next[next[j]]这在形式上很像状态转移。但算法界通常把它归为字符串匹配问题而不是典型的动态规划。这个分类争议的意义不在于站队而在于理解本质KMP的next数组构建确实利用了“已知结果推导未知结果”的递推思想但它缺少DP典型的“多阶段决策最优性”特征也没有在多个候选方案之间做选择更多是单纯的模式串自匹配推导。所以看到“递推”不要急着贴DP标签看到DP也不要害怕底层逻辑都是“用已知推未知”。这种思维迁移能力比纠结KMP算不算DP重要得多。6. 从斐波那契到更多DP模型思维扩展的路线图斐波那契模型是你动态规划的第一站绝不是最后一站。我把之后的几类经典DP模型按照依赖难度排了个序你应该按这个顺序逐步进阶。线性DP状态定义是线性的常见于编辑距离、最长递增子序列。它们的转移有的依赖前一个状态有的需要遍历之前所有状态比斐波那契的固定依赖复杂得多。区间DP典型如石子合并、矩阵链乘法。状态不仅包含起点还包含终点通常用dp[i][j]表示区间[i,j]的最优解转移需要枚举区间中间的分割点。背包DP01背包、完全背包、多重背包、资源分配问题。核心是“选/不选”的决策加上容量维度的约束。01背包的空间优化就是滚动数组的经典应用场。树形DP在树上做状态转移常见于“打家劫舍III”这类题目。每个节点的状态依赖其子节点遍历顺序是DFS自底向上。每个模型背后都有对应的数学结构和决策模式。但无论哪个模型起手式都一样定义状态、写转移方程、确认遍历顺序、处理边界条件。这四步你练熟了就能从“会做斐波那契”进化到“会做动态规划”。关于资源分配这类问题我再多说一嘴。很多人在学DP时觉得“资源分配”离自己很远其实它就是背包问题的广义形态你手里有一个总资源量要分给多个任务每个任务分配不同资源会带来不同收益问怎么分配总收益最大。状态定义里第一维是“处理到第几个任务”第二维是“已分配多少资源”转移时枚举当前任务分配多少。这不光在算法竞赛里常见在工程资源调度、预算分配里都能看到它的影子。学到这里你再回头看斐波那契就知道为什么它叫“基础模型”了——它的思想可以一路延伸到各种具体问题里。我个人在带新人时有个很深的体会很多人可以默写背包九讲却写不对一道难度中等的线性DP。原因就是他们跳过了斐波那契这个“地基模型”直接去啃复杂问题。地基没打好楼自然建不高。所以这一轮专题咱就从斐波那契老老实实开始把它吃透把状态定义和转移方程两件事练出肌肉记忆。下一专题我再深入讲背包模型到时候你会发现背包题里的很多代码结构和今天爬楼梯的滚动数组长得非常像——因为底层逻辑本来就是相通的。最后分享一个实操小技巧遇到任何DP题先在纸上画出状态转移表。以爬楼梯为例手动算一遍n从1到10的dp值你就能直观地看到每个状态怎么从前面两个状态“长”出来。这个习惯帮你建立DP的直觉远比看十篇题解有效。遇到实在没思路的新题也先列几个小数据手算往往算着算着状态定义和转移方程就浮出水面了。
吃透斐波那契，打通动态规划任督二脉：状态定义与转移方程
我见过太多人学动态规划第一反应就是去背状态转移方程。结果呢换个题目就不会了。背了dp[i] dp[i-1] dp[i-2]遇到爬楼梯、不同路径、解码方法照样两眼一抹黑。这事我以前也干过直到我重新把斐波那契数列模型彻底啃透才明白动态规划到底在干什么。斐波那契数列是什么F(0)0F(1)1F(n)F(n-1)F(n-2)。这是小学奥数就教过的数学递推。但它一旦放进算法的语境里就成了动态规划最标准的入门模型。数学递推解决的是“已知前两项求后一项”算法思维解决的是“怎么算最省时间、最省空间、最不容易出错”。这一篇文章我从斐波那契这个点切入讲清楚动态规划最核心的几条逻辑链路状态怎么定义、转移方程怎么列、遍历顺序怎么定、空间优化怎么做。不堆公式用你能直接跑的代码和能复现的思路来讲适合刚接触DP的算法初学者也适合那些背了很多方程但始终没打通任督二脉的选手。1. 从一道“会做的题”开始你真的懂斐波那契吗先别翻代码。我问你三个问题你能立刻答上来说明你确实懂了答不上来这篇文章你该仔细看看。问题一朴素递归求F(40)大概需要多少次函数调用问题二为什么dp数组的遍历顺序是0→n而不是n→0问题三为什么滚动数组只用两个变量就够了三个行不行四个行不行这三个问题分别对应重叠子问题、遍历顺序、空间优化。恰好就是动态规划三板斧。教科书上定义斐波那契数列只是给了个数学递推式F(0) 0 F(1) 1 F(n) F(n-1) F(n-2)n ≥ 2这个式子本身没有任何算法含量。它只说了一件事这一项由前两项决定。但你真拿它写递归会发现程序慢得像蜗牛。为什么看代码def fib(n): if n 1: return n return fib(n-1) fib(n-2)这段代码逻辑完全正确但效率极低。F(40)约需1.6亿次函数调用F(50)就要超过200亿次等到花儿都谢了。问题出在哪重复计算。你算F(40)的时候F(38)被算了三次F(35)被算了不知道多少次。这些重复计算白白浪费了CPU但斐波那契的递推结构恰好把这些重复暴露得明明白白这就是“重叠子问题”。动态规划解决的根本问题就是避免重复计算把已经算过的结果存起来下次直接用。2. 四种写法四个层次从递归到滚动数组斐波那契数列的实现几乎是学习DP实现演进的绝佳素材。我给新手上课时从来不讲什么高深理论就让他们把同一条题目用四种方法写出来写完自然就通了大半。2.1 朴素递归数学式子的最直接翻译最直观的写法就是上面那段Python代码纯粹把数学递推式翻译成代码。优点好写好理解。缺点慢到怀疑人生。复杂度分析一下T(n) T(n-1) T(n-2) O(1)展开后 T(n) O(2^n)。指数级复杂度n稍微大一点就彻底废了。这里需要留意的是这不是代码质量问题而是算法结构问题。哪怕换成C、Java只要结构是递归重复计算复杂度就不会变。很多人以为换个语言就能变快其实根本没抓住要害。2.2 记忆化搜索把重复计算缓存起来既然重复计算是元凶那我把每算过的结果存进字典或数组下次需要直接取不就行了吗def fib_memo(n): memo {0: 0, 1: 1} def helper(k): if k in memo: return memo[k] memo[k] helper(k-1) helper(k-2) return memo[k] return helper(n)这就是记忆化搜索也叫自顶向下的动态规划。递归入口是求F(n)然后向下拆到F(n-1)、F(n-2)直到基准情形。一旦某个子问题算过就存进memo后续直接读。复杂度立刻降到O(n)每个状态只算一次。但这里有一个极其重要的思维转变**memo里存的是什么是子问题的解。**这一步其实就是“状态”概念的雏形。memo[k]代表的就是第k个状态的值对应动态规划里“状态”这个词的含义。2.3 循环递推真正意义的动态规划递归记忆化虽然复杂度达标但递归本身有栈溢出风险而且会引入额外函数调用开销。更符合DP原教旨的做法是自底向上的循环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数组每个位置的值就是对应状态的最优解这个例子中没有“最优”单纯是解。为什么遍历顺序是从0到n因为状态转移的方向是向前依赖——要求dp[i]必须先有dp[i-1]和dp[i-2]。如果倒着遍历你算dp[n]时dp[n-1]和dp[n-2]还是未知的程序直接报错。这个道理看似简单却是DP遍历顺序问题的核心逻辑。2.4 滚动数组空间优化不是炫技观察递推式dp[i]只依赖dp[i-1]和dp[i-2]更早的状态用完之后再也用不到了。那何必开一整条数组用两个变量滚动覆盖就好。def fib_roll(n): if n 1: return n prev2, prev1 0, 1 for i in range(2, n 1): cur prev1 prev2 prev2, prev1 prev1, cur return prev1空间复杂度从O(n)降为O(1)。别小看这一步优化——后续很多DP题状态数组的规模直接从二维压到一维、从一维压到常数靠的就是滚动思想。比如背包问题里的空间优化本质上就是滚动数组的变体。这里需要强调空间优化的前提是状态转移只依赖相邻的几个状态。如果跳着依赖比如dp[i]依赖dp[i-3]那就得保留三个变量如果依赖全部历史状态那无法用滚动优化。每次动笔优化前先看转移方程依赖了哪些项。3. 斐波那契模型的核心状态定义是建模的第一步看懂了代码只是第一步。真正的分水岭在于如何从斐波那契数列抽象出一个通用的DP模型。很多初学者有个困惑为什么爬楼梯这道题是斐波那契题目是这样的每次可以爬1级或2级台阶问爬到第n级有多少种不同方法。设dp[i]为爬到第i级的方法数。到达第i级的方法要么从第i-1级直接上来要么从第i-2级跨两级上来。因此dp[i] dp[i-1] dp[i-2]这个式子和斐波那契一模一样。但注意问题语义完全不同斐波那契数列里F(n)就是数列的第n项爬楼梯里dp[i]代表的是“方法数”。同样的转移方程、不同的状态含义这就是模型迁移的本质。3.1 一个容易被忽略的问题递推方向由谁决定状态定义清楚之后递推方向不是拍脑袋定的而是由依赖关系决定的。原则只有一条计算当前状态所需的所有前置状态必须在之前已经算好。爬楼梯问题里dp[i]依赖dp[i-1]和dp[i-2]所以i从小到大遍历没问题。但有些题就需要反向遍历。比如后面学到背包问题dp[j] max(dp[j], dp[j-w[i]] v[i])如果正向遍历同一个物品会被重复放入多次那就变成完全背包了。所以01背包必须内层循环倒序遍历。这不是什么奇技淫巧而是严格由转移方程里状态依赖的方向决定的。斐波那契模型之所以适合入门正因为它的依赖方向简单直观——永远朝前看。你要借助这个简单场景把“由转移方程确定遍历顺序”这条方法论练成条件反射。3.2 模型迁移一爬楼梯代码实现时只需要微调边界条件。爬楼梯的问题里dp[0]通常设为1表示在第0级“一步不动”也算一种方案dp[1]1代表一步到第1级。def climb_stairs(n): if n 1: return 1 prev2, prev1 1, 1 for i in range(2, n 1): cur prev1 prev2 prev2, prev1 prev1, cur return prev1边界条件有讲究斐波那契数列从0开始F(0)0爬楼梯从1开始dp[0]1、dp[1]1最后返回dp[n]。边界值不同是因为两个问题的语义不同。不要拿到题就生搬硬套F(0)0那套先想清楚“下标为0代表什么”。3.3 模型迁移二不同路径LeetCode 62题机器人从m×n网格左上角走到右下角每次只能向下或向右问有多少条不同路径。设dp[i][j]为到达(i,j)的路径数。机器人只能从上方或左方过来所以dp[i][j] dp[i-1][j] dp[i][j-1]你仔细看这还是一维斐波那契的二维推广。每一格的转移只依赖相邻两格本质上还是“前两项求和”的思想只是从一维扩展到了二维。def unique_paths_with_obstacles(m, n): dp [[0] * n for _ in range(m)] dp[0][0] 1 if not obstacles[0][0] else 0 for i in range(m): for j in range(n): if not obstacles[i][j]: if i 0: dp[i][j] dp[i-1][j] if j 0: dp[i][j] dp[i][j-1] return dp[m-1][n-1]代码里的边界判断值得细品i0时加上方j0时加左方这样第0行和第0列就不用单独写初始化逻辑了。这个写法在DP题里非常常用能省掉一堆特殊情况的判断。3.4 模型迁移三解码方法LeetCode 91题“123”可以解码为“ABC”1,2,3或“LC”12,3问共有多少种解码方式。设dp[i]表示字符串前i个字符的解码方法数。第i个字符可以单独解码也可以和前一个字符合并解码单独解码要求字符在1~9之间此时dp[i] dp[i-1]合并解码要求前两个字符组成的数字在10~26之间此时dp[i] dp[i-2]def num_decodings(s): if not s or s[0] 0: return 0 n len(s) dp [0] * (n 1) dp[0], dp[1] 1, 1 for i in range(2, n 1): one int(s[i-1]) two int(s[i-2:i]) if 1 one 9: dp[i] dp[i-1] if 10 two 26: dp[i] dp[i-2] return dp[n]这道题比前两个例子高一个梯度因为它多了“条件转移”——不是所有情况下都能从上一个状态转移过来。但底层结构依然没脱出斐波那契模型的框架每个状态最多依赖前两个状态转移条件变了骨架还在。4. 从斐波那契看动态规划的三个基本性质斐波那契模型的价值远不止会做几道题。它把动态规划的三大性质展示得清清楚楚你在这个模型里感知到的每一条性质都能迁移到所有DP题目里。4.1 最优子结构大问题由小问题组合“最优子结构”这个术语很容易吓到新手。通俗解释大问题的最优解可以由子问题的最优解组合出来。斐波那契例子中F(5)的最优解就是它的值由F(4)F(3)构成而F(4)、F(3)本身又由更小的子问题构成。不存在说“为了求F(5)我得让F(4)取一个非最优值”。爬楼梯、最短路径、背包问题全都满足这个性质。判断一道题能不能用DP第一个问题就要问大问题和子问题之间是否存在这种“组合”关系比如求到第i级台阶的方法数能不能由到第i-1级和i-2级的方法数组合出来能那就DP不能想别的路子。4.2 无后效性过去不影响未来这是最抽象的一条也是初学者最容易绕晕的一条。无后效性的意思是某个状态一旦确定之后的状态只关心这个状态的值不关心它是怎么来的。斐波那契数列里F(5)等于多少只需要F(4)和F(3)的值至于F(4)是通过递归算出来的还是滚动数组算出来的根本不重要。历史路径完全不影响未来结果。这个性质决定了DP可以“无记忆地”递推。如果一道题里到达某个状态时你还需要知道“之前是怎么走的”那它就不是标准DP能解决的问题通常需要对状态进行扩充。比如状态不只存值还要存路径信息。无后效性是DP的护城河过不了这一关就不能用DP公式硬套。4.3 重叠子问题重复计算是优化的机会斐波那契的朴素递归慢慢在一模一样的子问题反复算。而DP的核心对策就是缓存子问题的解。判断一道题能否用DP第二个问题是否存在重叠子问题如果子问题完全不重叠那记忆化没有意义直接递归或分治就行。比如归并排序左右子数组排序相互独立没有重叠就不需要DP的缓存机制。斐波那契恰好把“重叠”这个概念具象化——画一棵递归树你肉眼可见F(38)被重复计算了好几次。在更复杂的题里这种重叠通常看不见要靠你分析转移方程时自己判断。5. 实操中的常见坑与排查技巧写DP题尤其在竞赛或者面试现场踩坑几乎是必经之路。这里分享几个我从斐波那契模型上遇到的问题和排查思路基本每一条在后续更复杂的DP题里都会遇到。5.1 状态定义不清晰我见过有同学写爬楼梯调了半天不对最后发现是dp数组的定义出了问题——他把dp[i]定义成“到第i级需要走的最小步数”但题目问的是“不同方案数”。定义错了转移方程全错代码怎么改都别扭。状态定义是DP的地基必须在动手前确认。我自己的习惯写注释把dp[i]的语义先写出来。比如# dp[i]: 到第i级台阶的爬法数量先把这句注释写好再写代码。表面上花十秒钟实际上能省掉后面十分钟的调试。做题多了你才会发现DP题百分之八十的难点在定义状态一旦定义对了转移方程往往水到渠成。5.2 溢出问题斐波那契数列增长极快F(50)约125亿F(100)约3.5e20。用C的intn超过46就溢出了。Python虽然有大整数不担心但换成其他语言很容易踩坑。解题时先估算下n的取值范围再决定用int还是long long必要时模一个大数如1e97。这也是很多题目明说“结果对10^97取模”的原因。否则你本地跑小数据都正确一旦提交大数据直接WA或者出现负数多半就是溢出。5.3 空间优化过早绕过误区不是所有题都该一上来就优化空间。很多新手看了滚动数组的写法觉得高端于是所有题都压缩成两个变量。结果状态定义改了以后需要保留一整条数组又把自己绕晕了。我的建议第一版代码先写完整的dp数组保证逻辑正确确认无误后再看转移方程依赖哪些状态决定能不能滚动。先对再优优化永远排在正确性之后。还有一点在回溯时通常需要保留全部状态不能滚动。比如要找具体路径而不是只求数量你压缩了数组就等于丢掉了历史信息。空间优化前先问自己后面要不要回溯。5.4 KMP到底是不是动态规划这是网络上经常被问到的问题。KMP算法里next数组的构建有递推关系例如在失配时next[j]next[next[j]]这在形式上很像状态转移。但算法界通常把它归为字符串匹配问题而不是典型的动态规划。这个分类争议的意义不在于站队而在于理解本质KMP的next数组构建确实利用了“已知结果推导未知结果”的递推思想但它缺少DP典型的“多阶段决策最优性”特征也没有在多个候选方案之间做选择更多是单纯的模式串自匹配推导。所以看到“递推”不要急着贴DP标签看到DP也不要害怕底层逻辑都是“用已知推未知”。这种思维迁移能力比纠结KMP算不算DP重要得多。6. 从斐波那契到更多DP模型思维扩展的路线图斐波那契模型是你动态规划的第一站绝不是最后一站。我把之后的几类经典DP模型按照依赖难度排了个序你应该按这个顺序逐步进阶。线性DP状态定义是线性的常见于编辑距离、最长递增子序列。它们的转移有的依赖前一个状态有的需要遍历之前所有状态比斐波那契的固定依赖复杂得多。区间DP典型如石子合并、矩阵链乘法。状态不仅包含起点还包含终点通常用dp[i][j]表示区间[i,j]的最优解转移需要枚举区间中间的分割点。背包DP01背包、完全背包、多重背包、资源分配问题。核心是“选/不选”的决策加上容量维度的约束。01背包的空间优化就是滚动数组的经典应用场。树形DP在树上做状态转移常见于“打家劫舍III”这类题目。每个节点的状态依赖其子节点遍历顺序是DFS自底向上。每个模型背后都有对应的数学结构和决策模式。但无论哪个模型起手式都一样定义状态、写转移方程、确认遍历顺序、处理边界条件。这四步你练熟了就能从“会做斐波那契”进化到“会做动态规划”。关于资源分配这类问题我再多说一嘴。很多人在学DP时觉得“资源分配”离自己很远其实它就是背包问题的广义形态你手里有一个总资源量要分给多个任务每个任务分配不同资源会带来不同收益问怎么分配总收益最大。状态定义里第一维是“处理到第几个任务”第二维是“已分配多少资源”转移时枚举当前任务分配多少。这不光在算法竞赛里常见在工程资源调度、预算分配里都能看到它的影子。学到这里你再回头看斐波那契就知道为什么它叫“基础模型”了——它的思想可以一路延伸到各种具体问题里。我个人在带新人时有个很深的体会很多人可以默写背包九讲却写不对一道难度中等的线性DP。原因就是他们跳过了斐波那契这个“地基模型”直接去啃复杂问题。地基没打好楼自然建不高。所以这一轮专题咱就从斐波那契老老实实开始把它吃透把状态定义和转移方程两件事练出肌肉记忆。下一专题我再深入讲背包模型到时候你会发现背包题里的很多代码结构和今天爬楼梯的滚动数组长得非常像——因为底层逻辑本来就是相通的。最后分享一个实操小技巧遇到任何DP题先在纸上画出状态转移表。以爬楼梯为例手动算一遍n从1到10的dp值你就能直观地看到每个状态怎么从前面两个状态“长”出来。这个习惯帮你建立DP的直觉远比看十篇题解有效。遇到实在没思路的新题也先列几个小数据手算往往算着算着状态定义和转移方程就浮出水面了。
