使用最小花费爬楼梯

难度: Easy

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

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

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

示例 1：

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

提示：

2 <= cost.length <= 1000
0 <= cost[i] <= 999

Submission

运行时间: 18 ms

内存: 16.1 MB

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        c=[0]*len(cost)
        c[-1]=cost[-1]
        c[-2]=cost[-2]
        for k in range(len(cost)-3,-1,-1):
            c[k]=cost[k]+min(c[k+1],c[k+2])
        return min(c[0],c[1])

Explain

这个题解使用动态规划的思路来解决问题。它从楼梯顶部开始，逆向计算到达每一层台阶的最小花费。对于每一层台阶，可以从它的前一层或前两层到达，因此取两者的最小值，再加上当前层的 cost 即可。最后返回起始的第一层和第二层的最小值。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # 初始化一个数组 c，用于存储每一层的最小花费
        c = [0] * len(cost)
        
        # 处理楼梯顶部的最后两层
        c[-1] = cost[-1]
        c[-2] = cost[-2]
        
        # 从倒数第三层开始，逆向计算每一层的最小花费
        for k in range(len(cost) - 3, -1, -1):
            # 当前层的最小花费为：当前层的 cost + 前一层和前两层中的最小值
            c[k] = cost[k] + min(c[k + 1], c[k + 2])
        
        # 返回起始的第一层和第二层的最小值
        return min(c[0], c[1])

Explore

在初始化数组c时，只设置了c[-1]和c[-2]的值，因为这两个值直接对应于楼梯的最后两个台阶的花费。这两个值是动态规划的基础，从这两个点开始向前计算其他所有台阶的花费。未初始化其他位置的值是因为在算法执行过程中，每个位置的值将基于之后的逻辑被计算出来。这种初始化方式确保了内存使用的效率，并且保证在计算每个台阶的最小花费时，所需的前两个值总是已经被计算过，从而避免了不必要的初始值设置。

逆向计算的思路基于的考虑是，最后两层的花费已知，可以从这些已知值出发，向前计算出到达每一层楼梯的最小花费。这种逆向方法可以让我们在计算时始终保持对所需数据的即时访问。从底部开始正向计算也是可行的，即从第一层和第二层开始，逐步计算到顶部的花费，但逆向计算可以直接利用数组的最后两个元素开始，避免了额外的边界条件判断，代码实现上更为直接和清晰。

边界条件c[-1]和c[-2]是直接对应于数组中的最后两个元素，即楼梯的最后两个台阶的花费。这两个边界条件是动态规划解决方案的起点，因为达到楼梯顶部的最小花费可以从这两个台阶开始逆向计算。它们的设定是为了确保在逆向计算过程中，每一步都能基于确定的最小花费进行下一步的计算。这种设置简化了问题的复杂性，并提供了一种清晰的方法来逐步解决问题。

该题解最后返回的是c[0]和c[1]的最小值，因为根据题目的设定，可以从第0层或第1层开始爬楼梯，且不需要支付其它额外的花费。因此，找到从这两个起点开始完成所有楼梯并达到楼顶的最小花费，就能确定整体的最小花费。由于动态规划确保了每一步都是基于最优解的决策，这种方法可以保证返回全局最低花费。