爬楼梯的最小成本

题目

爬楼梯的最小成本

信息

• 类型：问答
• 难度：⭐

考点

动态规划基础,状态转移方程,空间优化

快速回答

题目要求计算爬到楼梯顶部的最小成本，每次可以爬1或2阶台阶。

• 状态定义：dp[i]表示到达第i阶的最小成本
• 状态转移：dp[i] = cost[i] + min(dp[i-1], dp[i-2])
• 初始状态：dp[0] = cost[0], dp[1] = cost[1]
• 最终结果：min(dp[n-1], dp[n-2])
• 空间优化：只需保存前两个状态，空间复杂度O(1)

问题描述

给定一个整数数组 cost，其中 cost[i] 表示在第i阶楼梯需要支付的代价（索引从0开始）。每次可以爬1或2阶台阶，计算爬到楼梯顶部（越过最后一个台阶）的最小成本。起始点可以选择从索引0或1开始。

原理说明

动态规划的核心思想是将复杂问题分解为重叠子问题：

1. 最优子结构：到达第i阶的最小成本取决于前1阶和前2阶的最小成本
2. 状态定义：dp[i]表示到达第i阶的最小累计成本
3. 状态转移方程：dp[i] = cost[i] + min(dp[i-1], dp[i-2])
4. 边界条件：
   dp[0] = cost[0]（直接到达第0阶）
   dp[1] = cost[1]（直接到达第1阶）
5. 最终解：min(dp[n-1], dp[n-2])（顶部是第n阶，最后一步可能来自前1阶或前2阶）

代码示例

def minCostClimbingStairs(cost):
    n = len(cost)
    # 处理边界情况
    if n == 0: return 0
    if n == 1: return cost[0]

    # 初始化前两个状态
    prev1, prev2 = cost[0], cost[1]

    # 从第2阶开始迭代
    for i in range(2, n):
        current = cost[i] + min(prev1, prev2)
        prev1, prev2 = prev2, current  # 更新状态

    return min(prev1, prev2)  # 最后一步可能跳过最后一阶

# 示例测试
print(minCostClimbingStairs([10, 15, 20]))     # 输出：15（0→1→顶）
print(minCostClimbingStairs([1, 100, 1, 1, 1])) # 输出：3（0→2→4→顶）

最佳实践

• 空间优化：只保存前两个状态（prev1和prev2），空间复杂度从O(n)降至O(1)
• 边界处理：单独处理楼梯长度≤2的情况
• 正向迭代：从低到高计算，避免递归导致的重复计算
• 时间复杂度：O(n)，只需遍历一次数组

常见错误

• 错误初始化：忘记处理n=0或n=1的边界情况
• 状态转移错误：写成 dp[i] = min(dp[i-1], dp[i-2]) + min(cost[i-1], cost[i])（错误）
• 终点误解：最终返回dp[n-1]而忽略dp[n-2]也是有效终点
• 空间浪费：使用O(n)数组存储所有状态，未做空间优化

扩展知识

• 变形1：三步爬楼：若允许爬1/2/3阶，状态转移变为：dp[i] = cost[i] + min(dp[i-1], dp[i-2], dp[i-3])
• 变形2：路径记录：增加path数组存储最优路径选择
• 斐波那契关联：当cost全为1时，问题等价于斐波那契数列
• 自顶向下解法：记忆化搜索（递归+缓存），但迭代法通常更高效