1. 问题背景与核心理解
这道LeetCode 746题"使用最小花费爬楼梯"是一个经典的动态规划入门题目。题目描述为：给定一个整数数组cost，其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或两个台阶。你可以选择从下标为0或1的台阶开始爬楼梯，请计算并返回达到楼梯顶部的最小花费。
在实际开发面试中，这类动态规划问题出现的频率极高。我刚开始刷题时也在这类问题上栽过跟头，后来通过系统化的训练才掌握了其中的套路。这道题看似简单，但蕴含着动态规划的经典思考模式，特别适合用来理解最优子结构和状态转移的概念。
2. 动态规划解法详解
2.1 状态定义与转移方程
首先我们需要明确dp数组的含义。在这道题中，dp[i]表示到达第i级台阶所需的最小花费。注意这个定义非常关键，很多初学者容易在这里混淆"到达"和"站在"的区别。
根据题意，每次可以跨1或2个台阶，因此到达第i级台阶有两种方式：
- 从i-1级跨1步上来，花费为dp[i-1] + cost[i-1]
- 从i-2级跨2步上来，花费为dp[i-2] + cost[i-2]
因此状态转移方程为： dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
2.2 初始化与边界条件
初始化是动态规划最容易出错的部分。根据题意：
- dp[0] = 0 （可以从第0级开始，初始花费为0）
- dp[1] = 0 （也可以从第1级开始，初始花费为0）
这里有个易错点：虽然cost数组的下标从0开始，但dp数组需要考虑到达第0级和第1级的情况。
2.3 完整代码实现
def minCostClimbingStairs(cost): n = len(cost) dp = [0] * (n + 1) 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)。在面试中，面试官可能会追问如何优化空间复杂度。
3. 空间优化技巧
3.1 滚动数组优化
观察状态转移方程可以发现，dp[i]只依赖于dp[i-1]和dp[i-2]，因此我们可以只用两个变量来存储中间结果，而不需要维护整个dp数组。
优化后的实现：
def minCostClimbingStairs(cost): n = len(cost) prev, curr = 0, 0 for i in range(2, n + 1): next_val = min(curr + cost[i-1], prev + cost[i-2]) prev, curr = curr, next_val return curr这样空间复杂度就优化到了O(1)，这在处理大规模数据时非常有用。
4. 常见错误与调试技巧
4.1 初始化错误
最常见的错误是初始化不正确。比如有人会把dp[1]初始化为cost[0]，这是没有理解题目允许从第1级开始，初始花费应该是0。
调试技巧：在纸上画出前3个台阶的dp值，手动计算验证初始化是否正确。
4.2 数组越界
另一个常见错误是忘记dp数组的长度应该是n+1而不是n。因为要到达的是第n级台阶（顶楼）。
调试技巧：对于边界情况（如cost为空或只有1个元素）要特别测试。
4.3 状态定义混淆
有些人会把dp[i]定义为"站在第i级台阶的总花费"，这样会导致状态转移方程复杂化，容易出错。
经验法则：在爬楼梯问题中，dp[i]通常定义为"到达"而非"站在"的花费。
5. 问题变种与扩展
5.1 最多k步的爬楼梯
如果题目改为每次可以爬1到k步，该如何修改解法？这时状态转移方程变为： dp[i] = min(dp[i-j] + cost[i-j] for j in range(1, k+1) if i-j >=0)
5.2 不能连续跳相同步数
如果增加限制条件"不能连续两次跳相同的步数"，就需要在状态中额外记录上一步的跳跃距离。
5.3 实际工程应用
这类问题在实际中有很多应用场景，比如：
- 网络路由选择最小延迟路径
- 游戏中的最优路径规划
- 金融中的最优投资策略
6. 刷题建议与心得
通过这道题，我总结了几个动态规划的学习要点：
- 明确状态定义是关键，不同的定义会导致完全不同的解法
- 先写出暴力递归，再优化为记忆化搜索，最后转为递推
- 画状态转移图有助于理解问题
- 边界条件要单独测试
- 空间优化通常是最后考虑的事情
在实际面试中，建议按照以下步骤解答：
- 先说明暴力解法的时间复杂度
- 指出重复计算的问题
- 提出用动态规划优化
- 明确状态定义和转移方程
- 讨论初始化和边界条件
- 最后考虑空间优化
这道题虽然标为简单，但包含了动态规划的核心思想。我建议初学者至少做3遍：
- 第一遍理解题意和基本解法
- 第二遍尝试自己写出代码
- 第三遍思考优化和变种
