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级开始初始花费为0dp[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数组的长度应该是n1而不是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, k1) if i-j 0)5.2 不能连续跳相同步数如果增加限制条件不能连续两次跳相同的步数就需要在状态中额外记录上一步的跳跃距离。5.3 实际工程应用这类问题在实际中有很多应用场景比如网络路由选择最小延迟路径游戏中的最优路径规划金融中的最优投资策略6. 刷题建议与心得通过这道题我总结了几个动态规划的学习要点明确状态定义是关键不同的定义会导致完全不同的解法先写出暴力递归再优化为记忆化搜索最后转为递推画状态转移图有助于理解问题边界条件要单独测试空间优化通常是最后考虑的事情在实际面试中建议按照以下步骤解答先说明暴力解法的时间复杂度指出重复计算的问题提出用动态规划优化明确状态定义和转移方程讨论初始化和边界条件最后考虑空间优化这道题虽然标为简单但包含了动态规划的核心思想。我建议初学者至少做3遍第一遍理解题意和基本解法第二遍尝试自己写出代码第三遍思考优化和变种
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级开始初始花费为0dp[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数组的长度应该是n1而不是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, k1) if i-j 0)5.2 不能连续跳相同步数如果增加限制条件不能连续两次跳相同的步数就需要在状态中额外记录上一步的跳跃距离。5.3 实际工程应用这类问题在实际中有很多应用场景比如网络路由选择最小延迟路径游戏中的最优路径规划金融中的最优投资策略6. 刷题建议与心得通过这道题我总结了几个动态规划的学习要点明确状态定义是关键不同的定义会导致完全不同的解法先写出暴力递归再优化为记忆化搜索最后转为递推画状态转移图有助于理解问题边界条件要单独测试空间优化通常是最后考虑的事情在实际面试中建议按照以下步骤解答先说明暴力解法的时间复杂度指出重复计算的问题提出用动态规划优化明确状态定义和转移方程讨论初始化和边界条件最后考虑空间优化这道题虽然标为简单但包含了动态规划的核心思想。我建议初学者至少做3遍第一遍理解题意和基本解法第二遍尝试自己写出代码第三遍思考优化和变种
