746. 使用最小花费爬楼梯[easy]

https://leetcode-cn.com/problems/min-cost-climbing-stairs/

数组的每个索引作为一个阶梯，第 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。

注意：

cost 的长度将会在 [2, 1000]。
每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。

通过次数33,946 | 提交次数69,661

First Try

2020-06-11

这道题描述的场景有点莫名其妙，但还好找到了其中关键的结构，然后回忆起以前在哪里看过爬楼梯的问题，选择每种可能不停往上怼就行了。

对于走到第i步的最小总耗损，不管从哪里过来都需要承担第i步本身的耗损。而每次只能走1步或者2步，选择这两步中最小的一个作为起点即可。故第i步的最小耗损为mini_cost[i] = min(mini_cost[i-1], mini_cost[i-2]) + cost[i]。从i变成i-1和i-2，实现了状态的迁移，问题就有了解决的曙光。
起点位置明显就是0和1，终点选择则是终点前两个之间任意最小的一个。
bingo, 好久没有做得这么快的题目了，但是刚第一眼看到还是有点懵，还不习惯。

优化方向：时间复杂度为O(n), 空间方面依然是每次只是用缓存数组的两位，可以省略掉数组。

class Solution(object):
    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        if len(cost) <=1:
            return 0
        mini_cost = [-1 for i in range(len(cost))]
        mini_cost[0] = cost[0]
        mini_cost[1] = cost[1]
        for i in range(2, len(cost)):
            mini_cost[i] = min(mini_cost[i-1], mini_cost[i-2])  + cost[i]
        # print(mini_cost)
        return min(mini_cost[-2], mini_cost[-1])

测试

输入
[1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出
6
预期结果
6
stdout
[1, 100, 2, 3, 3, 103, 4, 5, 104, 6]

执行用时 :44 ms, 在所有 Python 提交中击败了84.01%的用户
内存消耗 :12.8 MB, 在所有 Python 提交中击败了50.00%的用户

746. 使用最小花费爬楼梯[easy]​

First Try​

746. 使用最小花费爬楼梯[easy]

First Try