刷动态规划的时候很多朋友会被“状态转移方程”五个字劝退总觉得这是数学天才才能想出来的东西。我最早学DP也这样后来发现与其硬啃一堆抽象理论不如盯住一个最简单的模型反复练。斐波那契数列模型就是那个最值得吃透的起点。今天这篇就来聊聊这个模型下的两道经典题“使用最小花费爬楼梯”和“解码方法”。前者一眼就能看出爬楼梯的影子后者藏得深一点但拆开之后依然是“当前结果由前两个状态推出来”的老套路。如果你是刚开始学DP或者题目刷了不少但一换场景就不会写转移方程这篇应该能帮你把思路理顺。1. 先搞清楚斐波那契数列模型是什么1.1 从斐波那契数列到状态转移斐波那契数列大家都很熟前两项是1和1从第三项开始每一项都等于前两项之和。用公式写就是 F(n) F(n-1) F(n-2)。很多刷题的人会觉得这是数学课的事跟算法题没关系。但实际上它就是动态规划里最干净、最典型的一个雏形。如果把斐波那契数列的求解过程改成动态规划的语言会发生什么事首先我们需要一个数组 dp让 dp[i] 表示第 i 项的值。然后我们规定初始条件 dp[0]1, dp[1]1。最后给出递推规则dp[i] dp[i-1] dp[i-2]。整个过程其实就三步定义状态、确定边界、写出转移方程。这也是所有动态规划题目的通用框架。我见过很多朋友一上来就背模板套“dp[i] max/min(dp[...] ...)”这种公式结果题目一变就懵。核心问题在于没有理解“为什么是前两个状态相加”。斐波那契数列模型里当前状态之所以只关心前两个状态是因为每次决策的“步长”最多只有两格或者当前情况的组合方式只有“用上一个结果”和“用上上一个结果”两种。只要这个结构在无论题目披着爬楼梯、跳格子、铺瓷砖还是解码字符串的外衣底层都是同一个套路。1.2 识别特征后一个结果依赖前两个结果那怎么识别一道题属于斐波那契数列模型我总结了一个比较简单粗暴的经验看它的决策过程是不是只有两种固定选择。比如爬楼梯每次可以跨1级或2级那么到达第 i 级的方案数只能来自第 i-1 级跨1步或者第 i-2 级跨2步。这里没有第三种可能所以 dp[i] dp[i-1] dp[i-2]。再比如“解码方法”一个字符可以单独解码也可以和前一个字符组成两位数解码。对于字符串的第 i 个位置它的解码方案同样只依赖于前 i-1 个字符单独解码当前字符或者前 i-2 个字符把当前字符和前一个字符组合解码。所以它也是两分支递推只不过每个分支都有额外条件限制。还有一个识别点是这类问题通常具有“无后效性”。简单说当前状态一旦确定之后怎么发展跟之前怎么来的已经没有关系了。斐波那契模型里dp[i] 只存“结果值”不存“路径”。比如走楼梯我们只关心到第 i 级有几种走法而不关心具体每一步踩在哪。解码方法也一样只关心前 i 个字符有多少种解码方式不关心具体解码成什么字母串。这种特性让状态转移变得非常简洁。所以当你看到一道题发现“当前位置/长度/状态”的答案只可能由它的前一个或前两个状态推导出来并且没有更复杂的条件分支时基本就可以往斐波那契模型上靠了。下面拿两道具体的题目来验证。2. 使用最小花费爬楼梯最直接的斐波那契应用2.1 题目场景与状态定义“使用最小花费爬楼梯”这道题在很多算法题集里都很常见。题面大概是这样的有一个楼梯每一级台阶都有一个非负的花费 cost[i]。你一开始可以选择站在下标为0或1的台阶上然后每次可以向上爬1级或者2级。当你爬过某一级台阶时就要支付对应台阶的花费。问爬到楼顶也就是越过所有台阶的最小花费是多少。这里有个细节特别容易让新手纠结爬过第 i 级要付费还是到达第 i 级就要付费其实两种理解都能做但必须前后一致。我习惯用“到达并准备向上走”的思路也就是当脚下站在第 i 级时已经为该级支付过 cost[i]。这样dp[i] 可以定义为“爬上第 i 级台阶的最小花费”。不过还有一个更不容易出错的定义方式也是我现在最推荐的dp[i] 表示到达第 i 层注意这里的 i 是楼层的概念0表示地面1表示第一级台阶以此类推所需的最小花费。这里的地面不需要任何花费所以 dp[0]0。同样因为一开始可以选择站在下标为0或1的台阶上所以到达第1级也不需要花费dp[1]0。为什么这个定义更舒服因为最终要求的是“爬到楼顶”楼梯顶部对应的是下标 n 的位置也就是 length(cost) 的位置。这样最后直接返回 dp[n] 就行不用再想着“最后一步落地免不免费”这种问题。2.2 状态转移方程与初始化推导现在来推导转移方程。假设我要到第 i 层也就是越过前 i 级台阶从0开始数cost 的下标是0到 n-1楼顶是第 n 层。要到达第 i 层只有两种可能第一种从第 i-1 层爬上1级。此时我首先要到达第 i-1 层花费 dp[i-1]然后踩上第 i-1 级台阶并支付 cost[i-1]所以总花费是 dp[i-1] cost[i-1]。第二种从第 i-2 层直接爬上2级。此时总花费是 dp[i-2] cost[i-2]。到达第 i 层的最小花费就是这两种方案里的较小值dp[i] min(dp[i-1] cost[i-1], dp[i-2] cost[i-2])初始化是 dp[0]0, dp[1]0。为什么 dp[1]0 而不是 cost[0]因为题目允许你一开始就站到第1级台阶上站上去不需要额外支付任何费用。只有当你从第0级往第1级走跨出那一步的时候才需要支付第0级的费用。这个区别很多人会漏掉。我拿一个例子手动推一遍。假设 cost [10, 15, 20]那么 n 3楼顶是第3层。dp[0] 0 dp[1] 0 dp[2] min(dp[1] cost[1], dp[0] cost[0]) min(0 15, 0 10) 10 dp[3] min(dp[2] cost[2], dp[1] cost[1]) min(10 20, 0 15) 15所以最小花费是15。路径是一开始站在第1级跳过第2级支付第1级的15然后爬上第3级楼顶。这样手动走一遍整个转移过程就非常清晰了。2.3 代码实现与空间优化按照上面的状态定义写代码很直接。先用数组版本方便理解def min_cost_climb(cost): n len(cost) dp [0] * (n 1) # dp[0]和dp[1]本来就是0不用额外处理 for i in range(2, n 1): dp[i] min(dp[i-1] cost[i-1], dp[i-2] cost[i-2]) return dp[n]这个版本正确但可以继续优化。因为计算 dp[i] 只用到 dp[i-1] 和 dp[i-2]根本不关心更早的状态。所以我们不需要一个长度为 n1 的数组只需要两个滚动变量。def min_cost_climb(cost): n len(cost) prev2, prev1 0, 0 # prev2对应dp[i-2], prev1对应dp[i-1] for i in range(2, n 1): cur min(prev1 cost[i-1], prev2 cost[i-2]) prev2, prev1 prev1, cur return prev1注意循环里 i 从2开始所以第一次循环时 prev2 dp[0]prev1 dp[1]这正好对应初始化。滚动的顺序也很有讲究必须先算 cur再用 cur 更新 prev1把旧的 prev1 丢给 prev2。如果反过来你还没用 prev1 计算 cur 就先把它覆盖了结果就全错了。2.4 这道题最容易踩的三个坑第一个坑把 dp 数组长度定义成 n而不是 n1。cost 下标是 0 到 n-1楼顶是第 n 层。如果 dp 只有 n 个元素最后返回 dp[n-1]那实际上你只算到了最后一级台阶还没算到“越过它之后”的楼顶。虽然在某些定义下也能凑出答案但一旦 cost 数组长度为1整个逻辑就乱了。建议统一成我上面这种“终点是第 n 层”的定义。第二个坑cost 下标的偏移。很多朋友写 dp[i] min(dp[i-1] cost[i], dp[i-2] cost[i-1])这种错位是因为把 dp 的下标和 cost 的下标搞混了。记住dp[i] 表示第 i 层要支付的是第 i-1 级台阶的费用因为第 i 层是越过前 i 级台阶之后的位置。可以在纸上画一条横轴标上 cost[0], cost[1], ..., cost[n-1] 和 dp[0], dp[1], ..., dp[n]画一次就不会错。第三个坑滚动变量更新顺序。我自己刚开始写滚动优化时出现过把 prev2, prev1 prev1, cur 写成 prev1, prev2 cur, prev1 的情况。这里一定要记住变量名的右边是旧值左边是新值。建议用中间变量 cur 先算好再一起赋值避免踩坑。3. 解码方法带条件的斐波那契递推3.1 题面拆解与状态含义“解码方法”看起来跟爬楼梯八竿子打不着实际上却是斐波那契数列模型里非常经典的一道变体。题面大致是有一个只由数字组成的字符串比如 226。现在要把它解码成由大写字母组成的字符串。解码规则是A 到 Z 分别对应数字 1 到 26。也就是说单个数字 2 可以解码为 B两个数字 22 也可以解码为 V因为 22 在 1 到 26 之间。问一共有多少种不同的解码方案。举个例子12 可以解码成 AB1对应A2对应B也可以解码成 L12对应L所以答案是2。再比如 226可以解码成 BBF2-2-6、VF22-6、BZ2-26一共3种。这道题的关键在于解码过程是一段一段切分的。当你看字符串的前 i 个字符时最后一个字符只能有两种处理方式自己单独解码成一个字母或者和它前面那一个字符拼在一起解码成一个字母。不可能三个字符拼在一起因为字母最多只对应两位数26。所以这是一个非常明显的“二分支递推”结构跟斐波那契数列一模一样。状态定义我推荐用 dp[i] 表示“字符串前 i 个字符 s[0:i] 有多少种解码方案”。注意这里的 i 是长度不是下标。举例来说dp[0] 表示空串dp[1] 表示只考虑第一个字符dp[n] 就是最终答案。这样定义的好处是在处理两位数字时直接用 s[i-2:i] 这个切片下标不会混乱。3.2 转移方程的分类讨论现在来推导 dp[i] 怎么由前面的状态得到。处理前 i 个字符时看最后一个字符 s[i-1]。第一种情况把它单独解码成一个字母。单独解码合法要求 s[i-1] 不能是 0因为数字0没有对应字母。如果合法那么前 i-1 个字符只需要已经成功解码也就是 dp[i-1] 种方案。所以在 s[i-1] ! 0 时dp[i] 需要加上 dp[i-1]。第二种情况把 s[i-1] 和 s[i-2] 凑成两位数然后解码成字母。这里有两个条件首先这个两位数必须在 10 到 26 之间。为什么不能是 01、05 这种因为如果十位是0那这个两位数字实际表示的是个位数而单独解码已经处理过了再拼成两位数反而会造成重复计算并且“05”也不对应任何字母。实际上合法两位数只有 10 到 26特别要注意 10 和 20 能解码成 J 和 T但 30 以上都不行。其次十位 s[i-2] 必须存在也就是 i 至少是2。如果条件满足前 i-2 个字符解码完成后把这两位当作一个整体解码所以 dp[i] 要加上 dp[i-2]。综合起来转移方程是dp[i] (s[i-1] ! 0 ? dp[i-1] : 0) (10 int(s[i-2:i]) 26 ? dp[i-2] : 0)初始化 dp[0] 1。这个1经常让人困惑空串为什么有一种解码方案其实这里把 dp[0] 当作一个“空前缀”的基准值。比如字符串 10当处理到 i2 时两位数字 10 合法那么 dp[2] 需要加上 dp[0]。如果没有 dp[0]1这件事就没法表达。另一个角度空串确实只有一种解码方式就是“什么都不解码”这在数学上方便成立。还要初始化 dp[1]。如果 s[0] ! 0dp[1] 1否则 dp[1] 0。这里如果 s 以0开头整个字符串肯定无法解码除非没有例外最终结果就会是0。3.3 代码实现与边界处理先写清晰易懂的数组版本def num_decodings(s): n len(s) if n 0 or s[0] 0: return 0 dp [0] * (n 1) dp[0] 1 dp[1] 1 for i in range(2, n 1): if s[i-1] ! 0: dp[i] dp[i-1] if 10 int(s[i-2:i]) 26: dp[i] dp[i-2] return dp[n]验证一下之前的例子 226dp[0] 1 dp[1] 12 i2s[1]2单独解码合法dp[2] dp[1] 得到1两位数是 22在10到26之间dp[2] dp[0] 得到2。 i3s[2]6单独解码合法dp[3] dp[2] 得到2两位数是 26在10到26之间dp[3] dp[1] 得到3。 结果3正确。数组版本写明白之后也可以做空间优化。这里比爬楼梯复杂一点因为两个分支是“可能发生”不是“一定发生”。但只要思路不变用两个变量滚动完全没问题def num_decodings(s): n len(s) if n 0 or s[0] 0: return 0 prev2 1 # dp[0] prev1 1 # dp[1] for i in range(2, n 1): cur 0 if s[i-1] ! 0: cur prev1 if 10 int(s[i-2:i]) 26: cur prev2 prev2, prev1 prev1, cur return prev1如果 n1循环不会执行直接返回 prev1。如果 s10初始化没问题i2时s[1]0单独解码不合法两位10合法curprev21返回1正确。如果 s100初始化 dp[1]1i2时s[1]0单独解码不合法两位10合法cur1prev21, prev11i3时s[2]0单独解码不合法两位00不合法cur0返回0正确。因为 100 确实无法解码1 不能拆10 后面跟 0 无法处理。3.4 常见错误和调试技巧解码方法最常见的错误是没有处理好数字0。比如给定 01很多新手会算成1实际上应该返回0。因为 0 不能单独解码而 01 也不是合法两位数。上面我加的 if s[0] 0: return 0 只能拦住开头是0的情况但后面出现0也需要在每个 i 里靠 s[i-1] ! 0 和两位范围判断来拦。第二个常见错误是两位数字的边界写错。只看 10 int(s[i-2:i]) 26其实是把 1 到 9 这种个位数排除了也把 27 以上的排除了。注意 int(01) 1但 1 不在 10 到 26 之间所以不会加上这就自动处理了前导零的情况。同理 int(10) 10合法。int(20)20合法。int(30)30不合法。所以这个区间写法比单独判断十位是不是0要省事得多。第三个错误是滚动变量更新顺序。在滚动版本里如果先更新 prev1 再用就全乱了。我建议每次循环先用 cur 把结果算完再统一移动 prev2、prev1不要边算边改。调试技巧方面我最喜欢用 dp 数组打印法。在数组版本里每算一个 dp[i] 就打印出来比对一下例子。比如 226 应该打印 [1,1,2,3]如果某个位置错了马上能定位到是哪一步转移出了问题。这比在脑子里空想要快得多。4. 两题对比斐波那契模型的通用套路4.1 从两道题看状态转移的统一写法把这两道题放在一起看非常有意思。对比维度使用最小花费爬楼梯解码方法状态定义dp[i]到达第 i 层的最小花费dp[i]前 i 个字符的解码方案数依赖前一个状态dp[i-1] cost[i-1]s[i-1]!0 时 dp[i-1]依赖前两个状态dp[i-2] cost[i-2]两位数字合法时 dp[i-2]合并方式取最小值求和初始值dp[0]0, dp[1]0dp[0]1, dp[1]0或1返回值dp[n]dp[n]可以看到它们的状态转移都只关心 dp[i-1] 和 dp[i-2]区别只有三点第一爬楼梯取 min解码方法求和第二爬楼梯的两个分支是无条件参与解码方法的分支分别有合法性要求第三解码方法多了一个 dp[0]1 的基准值设置。但只要把核心结构抽象出来你会发现它们就是一个“带条件判断的斐波那契”。这种抽象特别重要。刷题的时候最怕的就是每做一道题就觉得学了新东西然后继续背新模板。其实很多题的模板是同一个只是细节不同。如果你能从解码方法里看到爬楼梯的影子说明你对这个模型已经有一定理解了。我还喜欢把这类问题画成一张状态转移图一个节点指向它后面的两个节点就像二叉树从根往下长。爬楼梯是每个父节点都能到达两个子节点解码方法是某些边被条件切断了。图还是那张图只是有的路走不通。4.2 一通百通还能套用到哪些题斐波那契数列模型不只这两道题很多高频题目都是它的变体。我列几个典型的方便你刷题的时候对照。第一个是普通爬楼梯每次可以走1步或2步问到达楼顶的方案数。这就是最纯正的 dp[i] dp[i-1] dp[i-2]连条件都没有。第二个是打家劫舍一排房子不能偷相邻的两家问最大收益。它的转移是 dp[i] max(dp[i-1], dp[i-2] nums[i])。虽然是 max 而不是求和但同样只依赖前两个状态。这里的“不偷当前”相当于走了一步“偷当前且跳过前一个”相当于走了两步。第三个是粉刷房子每个房子可以刷三种颜色之一相邻房子颜色不能相同求最小花费。虽然多了一个颜色维度但如果把 dp[i][颜色] 展开每个颜色状态可能只依赖前一个房子的另外两种颜色本质上也是每步只有两个来源可以看作斐波那契模型的二维扩展。第四个是单词拆分不过它的转移依赖更复杂已经不是简单的 i-1 和 i-2 了这里提一下是为了说明只有当你判断“前一步/前两步”不足以覆盖所有决策时才需要换别的模型。斐波那契模型不是万能钥匙但覆盖面确实很广。我的经验是拿到一道动态规划题可以先问自己当前位置/状态的结果会不会只跟前一个、前两个状态有关如果会那就先把 dp[i-1] 和 dp[i-2] 写出来再看条件再看取 max 还是求和。这套流程能解决很多入门题。5. 刷题过程中的一点个人心得5.1 先写朴素版本再优化很多朋友一上来就追求空间复杂度 O(1)看到斐波那契模型就想滚动变量。我个人的建议是在理解和练习阶段不要急着省空间先把 dp 数组完整写出来。数组版的最大好处是每一步状态都留下来了你可以打印出来检查也能顺着表跟人讲清楚。等数组版彻底想明白了再花30秒改成滚动变量这个过程不只是优化还能让你对状态的依赖关系更敏感。有一次和一个朋友讨论“使用最小花费爬楼梯”他坚持要用 dp[i] 表示“站在第 i 级且已经付了 cost[i] 的最小花费”最后返回 min(dp[n-1], dp[n-2])。这个定义也没错但他写代码时一会儿加 cost 一会儿不减特别容易乱。我建议他改成“第 i 层”的定义把终点统一成 dp[n]他试了两道题之后觉得顺多了。所以不要把状态定义看作无关紧要的细节它决定了整个代码的清爽程度。5.2 怎么和别人讲清楚DP思路刷题和学习算法不是只有“做对”一个目标。能把自己会的题讲给别人听其实是一种更高层级的检验。我常用的讲法是按四步走第一步说清楚 dp[i] 代表什么第二步说清楚初始值是什么第三步写转移方程并解释每一个分支在描述什么第四步说清楚循环顺序和最终返回值。比如讲解码方法我会说dp[i] 是前 i 个字符的解码数。先初始化空串和第一个字符。然后每一轮看当前字符能不能自己走能走就加上 dp[i-1]再看它和前一个字符能不能组成两位数能走就加上 dp[i-2]。每一步的意思都在回答“最后一个字符怎么处理”而不是在背方程。这样讲对方一听就能跟上。我个人在刷题过程中还有个习惯每道题至少手动跑一个简单的例子不用长长度四五个元素就够。把 dp 数组从头到尾在纸上填一遍每个格子都写上怎么来的。这个过程很慢但特别锻炼手感。等你对斐波那契模型足够熟悉了看到一个字符串226脑子里会自动跑出 [1,1,2,3] 这条路径而不是条件反射地想去套模板。到现在我遇到新题还会先在纸上写“状态什么、dp[0]什么、dp[i]什么”三行字再往里面填细节。这套方法看着笨但确实帮我少走了不少弯路。