彻底掌握「爬楼梯的最小代价」问题：从递归到动态规划的进阶之路

在算法学习的旅途中，动态规划往往是我们面临的第一道坎。它不仅要求我们具备清晰的逻辑思维，还需要我们能从重叠的子问题中找到最优解的结构。今天，我想和你一起深入探讨一道非常经典，但同时也极具启发性的题目——「爬楼梯的最小代价」。

通过这篇文章，我们不仅仅是为了解决这一道题，更是为了学会一套完整的解题思维框架。我们将从最朴素的递归思路出发，一步步识别其中的性能瓶颈，通过记忆化搜索进行优化，最终推导出完美的动态规划解法。这个过程，正是你从「解题」走向「设计算法」的必经之路。

问题描述：不是简单的爬楼梯

在我们之前的算法练习中，你可能遇到过普通的「爬楼梯」问题：每次只能爬 1 或 2 个台阶，问有多少种方法爬到楼顶。那是一道关于排列组合的问题。

而今天我们要解决的问题，增加了一个现实世界的约束条件——代价。

题目详情：

给定一个整数数组 INLINECODE1d7e1ab6，其中 INLINECODE003fe433 是从楼梯第 i 个台阶向上爬需要支付的代价。一旦你支付了代价，你可以选择爬 一级 或 两级 台阶。

你可以选择从下标为 0 的台阶开始，或者从下标为 1 的台阶开始。

我们的目标：计算出到达楼层顶部的最低代价。

这里有一个关键点需要特别注意：我们需要到达的是「楼层顶部」，也就是数组越过最后一个台阶的位置。假设数组长度为 INLINECODEb6ee143d，那么我们的目标是到达第 INLINECODEb6f3330a 级台阶（虚拟的顶部位置）。

直观分析与示例拆解

在编写代码之前，让我们先用人脑模拟一下这个过程，确保我们真正理解了题意。

示例 1：简单起步

输入：cost = [10, 15, 20]

让我们分析一下所有可能的路径：

• 路径 A（从第 0 级开始）：

* 支付 10，站在第 0 级。

* 从第 0 级爬两级直接到顶部（因为数组长度为 3，顶部即下标 3）。

* 总代价：10。

• 路径 B（从第 0 级开始，慢慢爬）：

* 支付 10，站在第 0 级。

* 爬一级到第 1 级，需支付 15（累计 25）。

* 从第 1 级爬两级到顶部。

* 总代价：25。

• 路径 C（从第 1 级开始）：

* 支付 15，站在第 1 级。

* 从第 1 级爬两级直接到顶部。

* 总代价：15。

输出：min(10, 25, 15) = 15。

示例 2：复杂的决策

输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]

面对这种长数组，靠脑力硬算所有路径不仅累，而且容易错。这就是我们需要算法的原因。让我们试着找出一条低代价路径：

• 从下标 0 开始，代价 1。累计：1。
• 跳过昂贵的 100，爬两级到下标 2，代价 1。累计：2。
• 爬一级到下标 3，代价 1。累计：3。
• 爬两级到下标 5？不行，下标 5 代价是 100。我们爬一级到下标 4，代价 1。累计：4。
• 从下标 4 爬两级跳过 100，到达下标 6，代价 1。累计：5。
• 从下标 6 爬两级到达下标 8？不行，8 是 100。爬一级到下标 7，代价 1。累计：6。
• 从下标 7 爬两级到下标 9，代价 1。累计：7。
• 从下标 9 爬一级到顶部，代价 1。累计：8？等等。

让我们重新理清思路。实际上，最优解往往是跨越那些巨大的代价坑。

最优路径应该是：

• 起点 0 (Cost 1) -> 爬两级 -> 2 (Cost 1)。
• (Cost 1) -> 爬两级 -> 4 (Cost 1)。
• (Cost 1) -> 爬两级 -> 6 (Cost 1)。
• (Cost 1) -> 爬一级 -> 7 (Cost 1)。
• (Cost 1) -> 爬两级 -> 9 (Cost 1)。
• (Cost 1) -> 爬一级 -> 顶部。

总代价：1 + 1 + 1 + 1 + 1 + 1 = 6。

你看，只要避开那些 100 的代价陷阱，我们就能以极低的成本登顶。那么，如何让程序自动找到这条路呢？

解法一：暴力递归的尝试与反思

首先，让我们尝试使用最直观的递归思想。

思维逻辑

我们可以把问题倒过来想：要到达第 INLINECODE04c21925 级台阶（顶部），上一步一定是在第 INLINECODE213706e6 级或者第 i-2 级。

因此，到达 INLINECODE758ceaca 的最小代价 = INLINECODEc91ade64。

代码实现

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        # 从顶层（第 n 级）开始反推
        return self.min_cost(n, cost)
    
    def min_cost(self, i: int, cost: List[int]) -> int:
        # 基本情况：如果是第 0 级或第 1 级，不需要代价就能"站上去"
        if i == 0 or i == 1:
            return 0
        
        # 递归计算：
        # 路径1：从 i-1 迈一步上来，代价是 min_cost(i-1) + cost[i-1]
        # 路径2：从 i-2 迈两步上来，代价是 min_cost(i-2) + cost[i-2]
        return min(self.min_cost(i - 1, cost) + cost[i - 1], 
                   self.min_cost(i - 2, cost) + cost[i - 2])

为什么这还不够？

虽然逻辑是正确的，但如果你在 LeetCode 等平台上提交这段代码，很可能会收到「Time Limit Exceeded」（超时）的错误。

原因在于重复计算。想象一下，计算 INLINECODE14138b86 需要计算 INLINECODEe4315d0f 和 INLINECODE47fa3f47。而计算 INLINECODEdf599d71 时又要计算 INLINECODEe177b368 和 INLINECODEe5db7ae3。以此类推，min_cost(8) 会被计算无数次。这种指数级的时间复杂度 ($O(2^n)$) 是无法接受的。

解法二：记忆化搜索——空间换时间

既然重复计算是罪魁祸首，那我们只要把算过的结果记下来不就行了吗？这就是记忆化搜索。

优化策略

我们引入一个数组 memo，用来记录到达每一级台阶的最小代价。每次递归前，先查表：如果算过了，直接返回；没算过，算完后存入表。

代码实现

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        # 初始化记忆化数组，-1 代表未计算
        memo = [-1] * (n + 1)
        return self.min_cost(n, cost, memo)
    
    def min_cost(self, i: int, cost: List[int], memo: List[int]) -> int:
        if i == 0 or i == 1:
            return 0
        
        # 如果已经计算过，直接返回结果，避免重复递归
        if memo[i] != -1:
            return memo[i]
        
        # 计算并存入 memo 表
        memo[i] = min(self.min_cost(i - 1, cost, memo) + cost[i - 1], 
                      self.min_cost(i - 2, cost, memo) + cost[i - 2])
        return memo[i]

复杂度分析

现在，每个 INLINECODE6b1d8e28 从 0 到 INLINECODE32de1ab7 只会被计算一次。时间复杂度优化到了 $O(N)$，空间复杂度也为 $O(N)$（用于存储 memo 数组和递归栈）。这在大多数情况下已经可以通过测试了。

解法三：动态规划（自底向上）—— 迭代的艺术

虽然记忆化搜索解决了性能问题，但在工程实践中，我们通常更喜欢迭代的方式。这是因为递归深度过大时可能会导致栈溢出，且迭代的常数因子通常更小。

状态定义的澄清

这是这道题最容易混淆的地方。让我们明确一下 dp 数组的定义：

• INLINECODE9915bf06 的含义：到达第 INLINECODE296deb17 级台阶（站在台阶上，尚未支付离开该台阶的代价）所需要的最小累积代价。
• 边界条件：

* dp[0] = 0：可以直接从地面（起跑线）免费跳到第 0 级（或者说起始就在第 0 级）。

* dp[1] = 0：可以直接从地面免费跳两级到第 1 级（或者说起始就在第 1 级）。

• 最终目标：我们需要越过第 INLINECODE1d3d37be 级，到达 INLINECODEc0a0b43c（楼顶）。所以返回 dp[n]。

状态转移方程

对于第 INLINECODE6f28cc09 级台阶（INLINECODE017ac268），我们要想到达这里，只有两种前驱状态：

• 从 INLINECODE586e3124 级迈一步上来：总代价 = INLINECODEa587face (已在此处) + cost[i-1] (支付离开代价)。
• 从 INLINECODE0cff9d78 级迈两步上来：总代价 = INLINECODE0b4afd8e (已在此处) + cost[i-2] (支付离开代价)。

方程：dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

代码实现

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        # dp 数组大小为 n + 1，因为我们要算到第 n 级（顶部）
        dp = [0] * (n + 1)
        
        # 初始化 base case 已经隐含在初始化为 0 中了
        # dp[0] = 0, dp[1] = 0
        
        # 从第 2 级开始计算，直到第 n 级
        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]

这个解法非常稳健，时间复杂度 $O(N)$，空间复杂度 $O(N)$。

终极优化：空间复杂度降至 O(1)

作为追求极致的工程师，你会发现上面的代码其实有些浪费空间。在计算 INLINECODEe3aed121 时，我们只需要 INLINECODEa11e43f3 和 INLINECODE9e739f5e。再之前的数据（INLINECODE3b983b6c…）已经没有任何用了。

这意味着，我们不需要一个数组，只需要两个变量来滚动更新即可。

代码实现（极致版）

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # prev2 相当于 dp[i-2]，初始对应 dp[0] = 0
        # prev1 相当于 dp[i-1]，初始对应 dp[1] = 0
        prev2, prev1 = 0, 0
        
        # 我们需要计算 dp[2] 到 dp[n]
        for i in range(2, len(cost) + 1):
            # 计算当前阶梯的最小代价
            current = min(prev1 + cost[i - 1], prev2 + cost[i - 2])
            
            # 滚动更新变量，为下一次循环做准备
            # 新的 dp[i-2] 变成了旧的 dp[i-1]
            # 新的 dp[i-1] 变成了刚刚算出来的 current
            prev2, prev1 = prev1, current
            
        # 循环结束后，prev1 就是 dp[n]
        return prev1

这种优化为什么重要？

在面试中，当你写出 $O(N)$ 空间的解法后，面试官通常会追问："还能优化空间吗？"

如果你能敏锐地指出状态转移的「无后效性」，并给出 $O(1)$ 空间的解法，这会体现出你对数据结构的深刻理解和优秀的编码直觉。

常见错误与陷阱

在解决这个问题时，初学者往往会掉进以下几个坑：

• 数组越界：在编写 INLINECODEa6dd6a3c 循环时，容易混淆 INLINECODE6480b736 的结束点。记得我们要计算到 INLINECODEc976fe77（顶部），所以 INLINECODE508991ea 是正确的，而 range(2, n) 会漏掉最后一步。

• 状态定义混乱：很多人会纠结 INLINECODEe4e6cea2 到底是「到达 i 的代价」还是「离开 i 的代价」。建议：严格按照我们上面的定义，INLINECODEef92115c 表示「站在第 i 级台阶上」时的最小花费。要离开它去往更高处，才需要加上 cost[i]。

• 初始化错误：有些解法会直接将 INLINECODE458cb8ea 设为 INLINECODE01247bca，INLINECODEd0278f13 设为 INLINECODEddea56f4。这种解法通常逻辑会比较绕，容易导致错误。保持 dp[0]=0, dp[1]=0 是最符合物理直觉的（你可以理解为你是免费瞬移到起点的）。

总结与进阶思考

我们从最初的暴力递归，经历了记忆化搜索，最终到达了状态压缩的动态规划解法。这一步步的优化，其实就是计算机科学中「以空间换时间」再到「优化空间」的经典缩影。

核心要点回顾：

• 定义清晰：明确 dp[i] 的物理意义。
• 状态转移：找到 INLINECODE5bf7d7dd 与 INLINECODE06dc68e0、dp[i-2] 的关系。
• 滚动数组：当状态只依赖前几个状态时，优先考虑变量替代数组。

掌握了这道题，你其实已经拿到了解决类似路径问题的钥匙。比如「打家劫舍」问题，其核心逻辑与此题几乎一致：选还是不选，取决于哪个代价（收益）更优。

希望这篇文章能帮助你彻底吃透「最小代价爬楼梯」。多写几遍代码，感受那种变量滚动更新的节奏感，你会发现算法其实充满了逻辑之美。下次遇到类似的动态规划题目，相信你一定能从容应对！