1. 问题背景与核心理解这道LeetCode 746题看似简单实则蕴含了动态规划的经典思想。题目描述为数组cost表示爬上第i个台阶需要花费的体力值每次可以爬1或2个台阶可以从下标0或1开始求达到楼层顶部的最小花费。在实际编码面试中这类动态规划基础题出现频率极高。我遇到过不少候选人虽然能写出解法但对状态转移方程的推导过程含糊其辞。今天我们就从实际问题出发拆解这道题的思考全过程。2. 动态规划解法详解2.1 状态定义与初始化首先明确dp数组的含义。这里dp[i]表示到达第i个台阶所花费的最小体力。注意题目说达到楼层顶部所以需要虚构一个顶层即cost数组长度n对应的位置。初始化时需要考虑起始条件可以从0或1开始所以dp[0] cost[0], dp[1] cost[1]也可以选择从地面开始此时dp[0] 0, dp[1] 0两种初始化方式都可行# 方式一从台阶0或1开始 dp [0] * len(cost) dp[0], dp[1] cost[0], cost[1] # 方式二从地面开始 dp [0] * (len(cost)1) dp[0], dp[1] 0, 02.2 状态转移方程推导关键点在于理解状态转移的逻辑。到达第i个台阶有两种方式从i-1台阶跨1步上来花费dp[i-1] cost[i]从i-2台阶跨2步上来花费dp[i-2] cost[i]我们需要取这两种情况的最小值dp[i] min(dp[i-1], dp[i-2]) cost[i] # 方式一 # 或者 dp[i] min(dp[i-1]cost[i-1], dp[i-2]cost[i-2]) # 方式二2.3 完整代码实现以方式一为例的Python实现def minCostClimbingStairs(cost): n len(cost) dp [0] * n dp[0], dp[1] cost[0], cost[1] for i in range(2, n): dp[i] min(dp[i-1], dp[i-2]) cost[i] return min(dp[-1], dp[-2])注意最后返回需要比较最后两个台阶的值因为可以从倒数第二个台阶直接跨两步到顶。3. 空间优化技巧3.1 滚动数组优化观察状态转移方程发现dp[i]只依赖于前两个状态因此可以用两个变量代替整个数组def minCostClimbingStairs(cost): n len(cost) prev, curr cost[0], cost[1] for i in range(2, n): prev, curr curr, min(prev, curr) cost[i] return min(prev, curr)3.2 复杂度分析时间复杂度O(n)只需遍历一次cost数组空间复杂度优化后O(1)原始解法O(n)4. 边界条件与测试用例4.1 特殊输入处理空数组题目保证cost.length 2可不处理只有两个台阶直接返回min(cost[0], cost[1])三个台阶测试中间状态是否正确4.2 典型测试用例tests [ ([10,15,20], 15), # 最优路径15-20 ([1,100,1,1,1,100,1,1,100,1], 6), # 复杂路径 ([0,0,0,0], 0), # 全零情况 ([1,2], 1) # 最小长度 ]5. 常见错误与调试技巧5.1 易错点分析顶层处理不当忘记最后需要比较最后两个台阶初始化错误dp[1]直接赋值为cost[1]而忽略可以从0跨两步索引越界没有检查cost长度就直接访问dp[1]状态转移混淆把min(dp[i-1], dp[i-2])写成max5.2 调试建议打印dp数组观察每个步骤的状态变化画状态转移图用简单例子手动推导边界测试特别关注n2和n3的情况6. 算法扩展与变种6.1 变种题目每次可以爬1/2/3个台阶不能连续跳相同步数如不能连续两次跳两步带障碍物的爬楼梯类似LeetCode 636.2 实际应用场景游戏角色体力值计算资源分配最优路径投资组合的最小成本选择7. 个人实现心得在最初实现时我曾陷入一个思维误区认为必须从某个特定台阶开始。实际上题目允许从0或1开始这个理解偏差导致我最初的转移方程出错。后来通过画状态机图才恍然大悟。另一个经验是对于动态规划问题先写出暴力递归解法再优化往往比直接想状态转移更不容易出错。比如这道题可以先用递归思路def dfs(i): if i n: return 0 return cost[i] min(dfs(i1), dfs(i2))然后再通过记忆化优化为DP这种思考路径更加自然可靠。
1. 问题背景与核心理解这道LeetCode 746题看似简单实则蕴含了动态规划的经典思想。题目描述为数组cost表示爬上第i个台阶需要花费的体力值每次可以爬1或2个台阶可以从下标0或1开始求达到楼层顶部的最小花费。在实际编码面试中这类动态规划基础题出现频率极高。我遇到过不少候选人虽然能写出解法但对状态转移方程的推导过程含糊其辞。今天我们就从实际问题出发拆解这道题的思考全过程。2. 动态规划解法详解2.1 状态定义与初始化首先明确dp数组的含义。这里dp[i]表示到达第i个台阶所花费的最小体力。注意题目说达到楼层顶部所以需要虚构一个顶层即cost数组长度n对应的位置。初始化时需要考虑起始条件可以从0或1开始所以dp[0] cost[0], dp[1] cost[1]也可以选择从地面开始此时dp[0] 0, dp[1] 0两种初始化方式都可行# 方式一从台阶0或1开始 dp [0] * len(cost) dp[0], dp[1] cost[0], cost[1] # 方式二从地面开始 dp [0] * (len(cost)1) dp[0], dp[1] 0, 02.2 状态转移方程推导关键点在于理解状态转移的逻辑。到达第i个台阶有两种方式从i-1台阶跨1步上来花费dp[i-1] cost[i]从i-2台阶跨2步上来花费dp[i-2] cost[i]我们需要取这两种情况的最小值dp[i] min(dp[i-1], dp[i-2]) cost[i] # 方式一 # 或者 dp[i] min(dp[i-1]cost[i-1], dp[i-2]cost[i-2]) # 方式二2.3 完整代码实现以方式一为例的Python实现def minCostClimbingStairs(cost): n len(cost) dp [0] * n dp[0], dp[1] cost[0], cost[1] for i in range(2, n): dp[i] min(dp[i-1], dp[i-2]) cost[i] return min(dp[-1], dp[-2])注意最后返回需要比较最后两个台阶的值因为可以从倒数第二个台阶直接跨两步到顶。3. 空间优化技巧3.1 滚动数组优化观察状态转移方程发现dp[i]只依赖于前两个状态因此可以用两个变量代替整个数组def minCostClimbingStairs(cost): n len(cost) prev, curr cost[0], cost[1] for i in range(2, n): prev, curr curr, min(prev, curr) cost[i] return min(prev, curr)3.2 复杂度分析时间复杂度O(n)只需遍历一次cost数组空间复杂度优化后O(1)原始解法O(n)4. 边界条件与测试用例4.1 特殊输入处理空数组题目保证cost.length 2可不处理只有两个台阶直接返回min(cost[0], cost[1])三个台阶测试中间状态是否正确4.2 典型测试用例tests [ ([10,15,20], 15), # 最优路径15-20 ([1,100,1,1,1,100,1,1,100,1], 6), # 复杂路径 ([0,0,0,0], 0), # 全零情况 ([1,2], 1) # 最小长度 ]5. 常见错误与调试技巧5.1 易错点分析顶层处理不当忘记最后需要比较最后两个台阶初始化错误dp[1]直接赋值为cost[1]而忽略可以从0跨两步索引越界没有检查cost长度就直接访问dp[1]状态转移混淆把min(dp[i-1], dp[i-2])写成max5.2 调试建议打印dp数组观察每个步骤的状态变化画状态转移图用简单例子手动推导边界测试特别关注n2和n3的情况6. 算法扩展与变种6.1 变种题目每次可以爬1/2/3个台阶不能连续跳相同步数如不能连续两次跳两步带障碍物的爬楼梯类似LeetCode 636.2 实际应用场景游戏角色体力值计算资源分配最优路径投资组合的最小成本选择7. 个人实现心得在最初实现时我曾陷入一个思维误区认为必须从某个特定台阶开始。实际上题目允许从0或1开始这个理解偏差导致我最初的转移方程出错。后来通过画状态机图才恍然大悟。另一个经验是对于动态规划问题先写出暴力递归解法再优化往往比直接想状态转移更不容易出错。比如这道题可以先用递归思路def dfs(i): if i n: return 0 return cost[i] min(dfs(i1), dfs(i2))然后再通过记忆化优化为DP这种思考路径更加自然可靠。
