动态规划解决爬楼梯最小花费问题
1. 问题理解与场景拆解
这道LeetCode题目描述了一个经典的动态规划应用场景：假设你正在爬楼梯，每次可以选择爬1阶或2阶。每个台阶都有一个对应的"花费"值，当你踩上某个台阶时就需要支付对应的费用。题目要求计算爬到楼梯顶部的最小总花费。
实际工程中类似的场景比比皆是：比如游戏角色在不同路径中选择消耗最少金币的路线、物流配送中寻找成本最低的运输路径、甚至是生活中选择最省钱的购物方案。这类问题的核心都是在多阶段决策过程中，寻找全局最优解。
题目给出的示例非常直观：
- 输入cost = [10,15,20]
- 输出15 解释为：从下标为1的台阶开始，支付15，向上爬两阶到达顶部，总花费15。
2. 动态规划解法详解
2.1 状态定义与转移方程
我们定义dp[i]为到达第i个台阶所需的最小花费。这里有个关键点需要注意：题目描述的"顶部"实际上是第n个台阶之后的位置（n=cost.length）。因此我们需要计算的是dp[n]，而不是dp[n-1]。
状态转移方程推导如下：
- 要到达第i阶，只有两种可能：
- 从i-1阶跨1步上来，总花费=dp[i-1]+cost[i-1]
- 从i-2阶跨2步上来，总花费=dp[i-2]+cost[i-2]
- 取两者较小值即为dp[i]
因此状态转移方程为： dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
2.2 边界条件处理
初始状态需要特别注意：
- dp[0] = 0 （地面是起点，不需要花费）
- dp[1] = 0 （可以直接跨到第1阶，不经过任何台阶）
这里容易犯的错误是将dp[1]初始化为cost[0]。实际上根据题意，站在台阶上才需要支付费用，而选择从哪个台阶开始是不需要支付费用的。
2.3 空间优化技巧
观察状态转移方程可以发现，dp[i]只依赖于前两个状态dp[i-1]和dp[i-2]。因此我们可以用两个变量代替整个dp数组，将空间复杂度从O(n)优化到O(1)。
实现时使用prev和curr两个变量：
- prev表示dp[i-2]
- curr表示dp[i-1]
- 每次迭代计算next = min(curr + cost[i-1], prev + cost[i-2])
- 然后更新prev = curr, curr = next
3. 完整代码实现与逐行解析
def minCostClimbingStairs(cost: List[int]) -> int: n = len(cost) if n == 1: return cost[0] # 初始化前两个状态 prev, curr = 0, 0 for i in range(2, n + 1): # 计算下一步的最小花费 next_step = min(curr + cost[i-1], prev + cost[i-2]) # 滚动更新状态 prev, curr = curr, next_step return curr代码解析：
- 首先处理边界情况：当只有1个台阶时，直接选择从地面开始跨到顶部（不踩任何台阶）
- 初始化prev和curr为0，对应dp[0]和dp[1]
- 从i=2开始迭代到i=n（包含n）
- 每次计算下一步的最小花费，考虑从i-1跨1步或从i-2跨2步
- 滚动更新状态变量
- 最终curr即为dp[n]，即到达顶部的最小花费
4. 复杂度分析与变种讨论
4.1 时间复杂度分析
- 原始DP解法：O(n)，需要遍历整个cost数组一次
- 空间优化版：同样O(n)时间，但空间降为O(1)
4.2 相关变种问题
- 路径记录：如果需要输出具体路径而不仅是花费，可以额外维护一个数组记录每个状态的选择
- 三步爬楼：如果每次可以爬1、2或3阶，状态转移方程扩展为三项取最小
- 花费定义变化：如果花费是在离开台阶时支付而非踏上时支付，需要调整状态转移逻辑
- 带障碍版本：某些台阶不可达（花费为无穷大），需要在状态转移时加入判断
5. 常见错误与调试技巧
5.1 典型错误案例
边界条件错误：
- 错误地将dp[1]初始化为cost[0]
- 忘记处理n=1的特殊情况
索引越界：
- 在循环中错误地访问cost[-1]
- 没有正确处理i-2可能为负的情况
状态转移混淆：
- 混淆"踏上台阶"和"跨越台阶"的花费计算时机
- 错误地将dp[n]当作最终结果（实际应为dp[n+1]）
5.2 调试建议
- 先用小例子手动计算dp数组，验证思路
- 打印中间状态变量，观察其变化是否符合预期
- 特别注意循环的起始和终止条件
- 对于空间优化版本，可以先用标准DP实现，再逐步优化
6. 实际工程应用扩展
虽然这是一个算法练习题，但其核心思想在工程中有广泛应用：
- 资源调度优化：在有限资源下选择最优任务执行路径
- 游戏AI决策：NPC寻找消耗最低的行动路线
- 金融投资策略：在多阶段投资中选择成本最低的方案
- 网络路由选择：寻找延迟最小的数据传输路径
理解这类问题的关键在于：
- 准确识别"阶段"（台阶）
- 明确定义"状态"（到达某个阶段的花费）
- 正确建立状态转移关系（选择策略）
在实际编码面试中，面试官可能会要求解释状态转移方程的含义，或者讨论如何修改条件来适应不同的场景。因此不仅要会写代码，更要理解每个决策背后的逻辑。