刷 LeetCode 的朋友应该都遇到过这个经典标题746. 使用最小花费爬楼梯。我在刷动态规划专题的时候把这道题放在很靠前的位置因为它属于“一眼能看出是 DP但写起来容易栽跟头”的题目。难度标的是简单但如果你没把状态定义想清楚很容易在返回值和初始化上卡半天。这道题的核心就是最小花费爬楼梯给你一个数组cost每个台阶往上爬要付对应的体力值你可以从第 0 级或第 1 级开始每次能爬 1 步或 2 步问爬到楼顶最少要花多少。它其实是一个典型的动态规划问题而且是非常适合入门的线性 DP。不管你是刚开始刷题的新手还是准备面试前想快速过一遍经典题这篇都值得看完。1. 先把题目读透这道题究竟在考什么1.1 为什么你能判断出这是动态规划题判断一道题是不是动态规划我个人的习惯是看三点有没有“最值”要求、决策是否分阶段、后续状态是否只依赖前面的状态。这道题三个条件全占。第一“最少花费”直接命中最优子结构第二每次爬楼梯要决定跨 1 步还是跨 2 步这是一个连续决策过程第三当你站在第i级台阶时之前怎么走到第i-1级、第i-2级的细节根本不影响你后面怎么走。这种“过去的路径不影响未来决策”的性质就是动态规划里的无后效性也是能做 DP 的前提。很多新手拿到题会先想“我是不是要用 DFS 把所有走法列出来”这就是没抓住无后效性。一旦你意识到站在当前位置只需要看前一个和前两个位置的最优值这道题的复杂度就从指数级降到了线性。1.2 这道题和经典爬楼梯题的亲戚关系LeetCode 70 题“爬楼梯”是问“有多少种方式爬到楼顶”而 746 题是问“最少花多少体力到楼顶”。它们的状态转移长得很像都是dp[i]由dp[i-1]和dp[i-2]推导而来区别只是 70 题用加法累加方案数746 题用min求花费最小值。我建议你把这两道题放在同一天刷因为它们的框架完全一致。70 题你能写出dp[i] dp[i-1] dp[i-2]那 746 题你只要把加号换成min再加上对应台阶的 cost 就行。这种“同框架换语义”的训练方式比单独刷十道题更能帮你建立动态规划的题感。2. 核心推导状态定义与状态转移方程2.1 状态定义的两套方案我做动态规划题有一个习惯先写两版状态定义选一个最不容易出错的。746 题有两种主流定义方案 Adp[i]表示到达第i级台阶的最小花费不包含第i级往上爬的花费。方案 Bdp[i]表示离开第i级台阶即从第i级往上爬之后的最小累计花费包含cost[i]。方案 A 的答案是dp[n]其中n是cost.length因为楼顶是第n级方案 B 的答案是min(dp[n-1], dp[n-2])因为最后可以从倒数第一级或倒数第二级直接跨到楼顶。我个人更推荐方案 A逻辑更直白也更好解释。对比项方案 A方案 B状态含义到达第 i 级时已花费离开第 i 级时已花费是否包含 cost[i]不包含包含初始化dp[0]0, dp[1]0dp[0]cost[0], dp[1]cost[1]最终答案dp[n]min(dp[n-1], dp[n-2])两套方案都能 AC但方案 A 不容易把“到达”和“离开”搞混新手建议从方案 A 入手。2.2 状态转移方程的推导过程以方案 A 为例我要到达第i级台阶只能从两个地方过来从第i-1级爬 1 步先到达i-1级花dp[i-1]再支付cost[i-1]才能从i-1级爬上来。从第i-2级爬 2 步先到达i-2级花dp[i-2]再支付cost[i-2]才能从i-2级跨上来。因为要求最小花费所以取两者较小的那个dp[i] min(dp[i-1] cost[i-1], dp[i-2] cost[i-2])这里的关键点是支付cost[i-1]的动作发生在从第i-1级往上爬的那一刻而不是停留在第i-1级的那一刻。很多教程把这句含糊带过导致初学者搞不懂“为什么 dp[i] 要加上 cost[i-1] 而不是 cost[i]”。你只要记住一个原则cost 是“爬”的费用不是“站”的费用这个方程就永远不会写错。2.3 初始化与边界条件的来龙去脉方案 A 里dp[0]表示站在第 0 级台阶的最小花费。因为题目允许直接从第 0 级开始爬所以站在起点不需要花任何钱dp[0] 0。同理dp[1]表示到达第 1 级台阶的最小花费。你既可以先到第 0 级再爬上第 1 级也可以直接选择从第 1 级开始爬因此dp[1] 0。这是最容易出错的地方之一。我记得第一次做这道题时把dp[1]设成了cost[1]理由是“到第 1 级总要付钱吧”。但题目说的很清楚你可以选择从下标为 0 或下标为 1 的台阶开始爬。既然能从第 1 级出发那到达第 1 级这个动作就不存在花费自然为 0。另外要注意dp数组的长度是n 1而不是n。因为当你在cost的最后一级台阶上再迈一步或两步时就已经到达楼顶了这个“楼顶”在数组里是第n级需要dp[n]来承载结果。漏掉这个位置要么越界要么答案少算一级。3. 代码实现从基础版到空间优化3.1 基础版一维 DP 数组先把逻辑跑通我先给你看最容易理解的版本用一维数组存所有状态class Solution: def minCostClimbingStairs(self, cost: List[int]) - int: n len(cost) dp [0] * (n 1) dp[0] 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]拿示例cost [10, 15, 20]手算一遍dp[0] 0dp[1] 0dp[2] min(dp[1] cost[1], dp[0] cost[0]) min(0 15, 0 10) 10dp[3] min(dp[2] cost[2], dp[1] cost[1]) min(10 20, 0 15) 15答案是 15。最优路径是站在第 1 级不花钱花cost[1] 15爬 1 步到第 2 级不对这里要注意你的下标。dp[3]表示楼顶路径是从第 1 级花 15 直接跨越 2 步到楼顶或者从第 0 级花 10 到第 1 级再花 20 到楼顶总花费 30。所以最小是 15。这个版本的时间复杂度是O(n)空间复杂度是O(n)适合面试时先讲思路再写代码的阶段因为它的每一步都跟状态转移方程一一对应面试官更容易跟你的思路走。3.2 空间优化版滚动变量把空间降到 O(1)观察状态转移方程你会发现dp[i]只依赖dp[i-1]和dp[i-2]更早的状态根本用不上。既然只关心前两个状态完全可以用两个变量滚动更新没必要开一整个数组class Solution: def minCostClimbingStairs(self, cost: List[int]) - int: n len(cost) prev 0 # dp[i-2] curr 0 # dp[i-1] for i in range(2, n 1): next_dp min(curr cost[i - 1], prev cost[i - 2]) prev, curr curr, next_dp return curr这段代码的核心就是循环里的交换每次算出新的next_dp后把原来的curr变成新的prev把next_dp变成新的curr。这个操作本质上就是“状态平移”是动态规划空间优化里最常用的套路后面做大数背包、最长公共子序列时还会反复遇到。空间优化版的复杂度是O(n)时间、O(1)空间。实际刷题时如果你能直接写出这个版本会给面试官留下“对 DP 优化有意识”的印象。但如果你对滚动变量还不太熟我建议先写基础版AC 后再改成滚动变量不要一上来就炫技反而把自己绕晕。3.3 原数组就地修改的另一种状态定义还有一种写法也很常见直接在cost数组上改用方案 B 的思想class Solution: def minCostClimbingStairs(self, cost: List[int]) - int: n len(cost) for i in range(2, n): cost[i] min(cost[i - 1], cost[i - 2]) return min(cost[n - 1], cost[n - 2])这个版本里cost[i]被改造成“离开第 i 级所需的最小累计花费”包含第i级本身的费用。循环从i 2开始因为前两级已经初始化好不需要改。最后返回min(cost[n-1], cost[n-2])对应从倒数第一级或倒数第二级直接迈到楼顶这两种结束方式。必须提醒你的是这种写法会修改原始数组。如果在实际工程里cost后面还要复用这就是个 bug但在 LeetCode 刷题场景下通常没问题。我用这个写法主要图它省事但给别人讲题时还是会回到方案 A因为方案 A 更贴近题目语义不容易误解。4. 常见问题与易错点排查4.1 初始化就出错的三种典型写法我见过不少人在初始化上翻车最典型的三种dp[1] cost[1]把“到达第 1 级”和“从第 1 级出发”混淆了。dp[0] cost[0]忽略了题目允许从第 0 级开始爬站在起点不花钱。数组长度写成n忘了楼顶是第n级结果dp[n]越界。这三种错误的共同根源就是没想清楚“cost 什么时候付”。我后来养成了一个习惯写状态定义时在注释里写清楚“dp[i] 代表什么、不包含什么”再写代码。注释能强迫你把语义理顺很多低级错误都能在写注释阶段自我纠正。4.2 返回值搞混dp[n] 还是 min(dp[n-1], dp[n-2])这是区分两套状态定义的关键。如果你用方案 A答案就是dp[n]因为n就是楼顶的位置。如果你用方案 B答案就是min(dp[n-1], dp[n-2])因为你离开最后一级台阶后还要再迈一步才到楼顶。我见过有人把两套方案混用用方案 A 的方程却返回min(dp[n-1], dp[n-2])导致结果偏差。要避免这个问题最有效的办法是在草稿纸上先写出状态定义再写转移方程最后写返回值按这个顺序自查一遍。如果状态定义写的是“到达”那返回的就是“楼顶”如果状态定义写的是“离开”那返回的就是“最后两级的最小值”。4.3 从递归到记忆化再到迭代的演进还有一部分人会第一时间想到递归解法定义一个函数f(i)表示到达第i级的最小花费然后递归调用f(i-1)和f(i-2)。这个思路本身没错但纯递归会有大量重复计算时间复杂度是O(2^n)在n稍大时直接超时。如果你习惯递归思考我建议加一个记忆化数组from functools import lru_cache class Solution: def minCostClimbingStairs(self, cost: List[int]) - int: n len(cost) lru_cache(None) def dfs(i): if i 1: return 0 return min(dfs(i - 1) cost[i - 1], dfs(i - 2) cost[i - 2]) return dfs(n)这种“自顶向下”的写法思路清晰但有函数调用开销而且lru_cache在工程里不如迭代版本直观。我的建议是面试时先用递归思路解释再改写成迭代版本一方面展示你理解递归本质另一方面体现你能把思路落成高效的代码。刷题阶段最终还是要以迭代为主。快速排查表症状可能原因修复方式返回结果比预期小初始化 dp[1] 为 0 后忘记考虑必须支付起点费用检查状态定义是否一致返回结果比预期大把 cost 的某个值重复计算了检查转移方程中 cost 下标数组越界dp 数组长度写成 n改成 n1超时用了无记忆化的递归改记忆化或迭代5. 从这道题到 0-1 背包动态规划的进阶路线5.1 为什么说这是入门 DP 的第一道题很多人提到动态规划就想到 0-1 背包、最长递增子序列这些经典题但我觉得真正的起点应该是 746 这种简单线性 DP。它只有一个状态维度转移方程只有一个min初始化规则也不复杂刚好卡在“能听懂”和“有挑战”之间。我在带新人刷题时会让他们按照这个顺序来先做 70 题爬楼梯再做 746 题最小花费爬楼梯然后做 198 题打家劫舍。这三道题难度递增但共用同一个框架定义dp[i]找到前序状态到当前状态的关系最后处理边界。把这个框架走熟之后再看区间 DP、背包 DP就不会觉得每个题都是全新的知识体系。5.2 动态规划刷题路线建议从我自己的经验来看动态规划的学习可以分成四个阶段线性 DP 入门爬楼梯、最小花费爬楼梯、打家劫舍、等差数列划分。二维 DP 与路径问题不同路径、最小路径和、编辑距离这个阶段开始接触二维dp数组需要自己画表格推导。背包问题0-1背包、完全背包。这里重点理解“遍历顺序”的含义——为什么 0-1 背包要倒序遍历容量为什么完全背包可以正序。状态压缩与高级 DP状压 DP、树形 DP、数位 DP面试考得少但难点题会碰到。有人总爱跳阶段直接背 0-1 背包的模板结果面试时被追问“为什么这里要j--”就卡住了。你先搞懂 746 题的滚动变量优化再回头看 0-1 背包的倒序遍历会发现它们本质上是同一个优化思想用一个数组存状态时为了避免覆盖还需要使用的旧状态就得小心遍历方向。这就是为什么我强调要把基础题吃透因为它后面的道理是通用的。6. 最后分享一点我的做题习惯这道题我前前后后刷过不下五遍每次重刷都会有一点新体会。最近一次重刷时我把三种写法都写了一遍然后仔细对比了它们的空间复杂度和适用场景。我发现自己早期刷题最大的问题是“AC 就对答案”而不是“把每个解法吃透”。后来我改成刷每一道题都强迫自己写两种以上的解法并搞清楚它们之间的等价关系。746 就是一个特别适合做这种练习的题目基础的 DP 数组、滚动变量、就地修改三种写法各有各的味道但背后是同一个状态转移。如果你刚开始学动态规划我建议你把这题放到“必做清单”里先按我给的步骤一步步推导再自己默写代码最后思考如果cost数组特别大还有没有更优的解法。你能把这道题讲到别人听懂动态规划的第一步就算真正迈出去了。