LeetCode 746 - 使用最小花费爬楼梯

题目描述

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

1. 问题分析

这是爬楼梯问题的变体，主要区别是：

每个台阶都有一个花费
可以从索引0或1开始
目标是到达顶部（数组长度位置）的最小花费

2. 解题思路

状态定义

dp[i] 表示：到达第i个台阶的最小花费

状态转移方程

dp[i] = min(dp[i-1], dp[i-2]) + cost[i]

解释：到达第i个台阶可以从：
- 第i-1个台阶爬1步上来
- 第i-2个台阶爬2步上来
选择这两种方式中花费较小的一种

代码实现和详细解释

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # 例如：cost = [10, 15, 20]
        # dp数组长度等于cost长度
        dp = [0] * len(cost)
        
        # 初始化前两个台阶的花费
        dp[0] = cost[0]  # 第一个台阶的花费
        dp[1] = cost[1]  # 第二个台阶的花费
        
        # 从第三个台阶开始计算最小花费
        for i in range(2, len(cost)):
            # dp[i-1]：从前一个台阶爬1步上来的花费
            # dp[i-2]：从前两个台阶爬2步上来的花费
            # cost[i]：当前台阶的花费
            dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
        
        # 为什么返回min(dp[-1], dp[-2])？
        # - dp[-1]是最后一个台阶的最小花费
        # - dp[-2]是倒数第二个台阶的最小花费
        # - 可以从这两个位置中的任意一个跳到顶部
        # - 选择较小的那个即可
        return min(dp[-1], dp[-2])

# 空间优化版本
def minCostClimbingStairs(self, cost: List[int]) -> int:
    # 只需要记住前两个状态
    prev2, prev1 = cost[0], cost[1]
    
    # 从第三个台阶开始
    for i in range(2, len(cost)):
        # 计算当前台阶的最小花费
        current = min(prev1, prev2) + cost[i]
        # 更新状态
        prev2, prev1 = prev1, current
    
    # 返回最后两个状态的较小值
    return min(prev1, prev2)

示例解析

假设输入：cost = [10, 15, 20]

初始化：
- dp[0] = 10 (第一个台阶花费)
- dp[1] = 15 (第二个台阶花费)
计算dp[2]：
- 从dp[0]跳两步：10 + 20 = 30
- 从dp[1]跳一步：15 + 20 = 35
- dp[2] = min(30, 35) = 30
最终结果：
- dp[-1] = dp[2] = 30
- dp[-2] = dp[1] = 15
- return min(30, 15) = 15