746.使用最小花费爬楼梯 Min Cost Climing Stairs

Myth丶恋晨 2022-12-29 11:19 114阅读 0赞

## 题目描述 ##

数组的每个索引作为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值  c o s t \[ i \] cost\[i\] cost\[i\](索引从0开始)。每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。

**示例 1**:

> 输入: cost = \[10, 15, 20\]  
> 输出: 15  
> 解释: 最低花费是从cost\[1\]开始，然后走两步即可到阶梯顶，一共花费15。

**示例 2**:

> 输入: cost = \[1, 100, 1, 1, 1, 100, 1, 1, 100, 1\]  
> 输出: 6  
> 解释: 最低花费方式是从cost\[0\]开始，逐个经过那些1，跳过cost\[3\]，一共花费6。

来源：力扣（LeetCode）[链接][Link 1]

## 题解 ##

离最终题解只差一步之遥，参考了大佬的题解，这道题属于动态规划问题，有以下两种解题思路：

**解法一**：  
执行用时：60 ms, 在所有 Python3 提交中击败了97.30%的用户；  
内存消耗：14.9 MB, 在所有 Python3 提交中击败了5.15%的用户。

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

**解法二**：  
执行用时：52 ms, 在所有 Python3 提交中击败了99.94%的用户；  
内存消耗：14.7 MB, 在所有 Python3 提交中击败了5.15%的用户。

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

参考博客：[动态规划问题 - 经典模型的状态转移方程][-]

[Link 1]: https://leetcode-cn.com/problems/min-cost-climbing-stairs
[-]: https://www.cnblogs.com/tgycoder/p/5037559.html