leetcode 每日一题：746. 使用最小花费爬楼梯

用户7685359

发布于 2020-12-23 12:49:43

3170

发布于 2020-12-23 12:49:43

文章被收录于专栏：FluentStudyFluentStudy

leetcode 每日一题：746. 使用最小花费爬楼梯：https://leetcode-cn.com/problems/min-cost-climbing-stairs/

一起刷题吧

一、题目分析

输入：由数值组成的数组输出：到达楼层顶部的最低花费难度：简单标签：贪心，动态规划

示例 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。

二、参考代码

这个题是动态规划里比较简单的题目，动态方程也比较好想：

F[i] 表示走到第 i 层需要的最小的步数，只是走到 F[i] = min(F[i-1] + cost[i-1], F[i-2] + cost[i-2]) 最终结果是 F[len(cost)] 即走过第 len(cost)-1 层

参考代码如下：

from typing import List


class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        if not cost:
            return 0
        # F[i] 表示走到第 i 层需要的最小的步数，只是走到
        # F[i] = min(F[i-1] + cost[i-1], F[i-2] + cost[i-2])
        # 最终结果是 F[len(cost)] 即走过第 len(cost)-1 层

        F = [0] * (len(cost) + 1)

        for i in range(2, len(cost)+1):
            F[i] = min(F[i-1]+cost[i-1], F[i-2] + cost[i-2])
        return F[-1]

对空间做优化，只需要前两次的状态，不需要使用一个数组，优化代码如下：

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        if not cost:
            return 0
        # F[i] 表示走到第 i 层需要的最小的步数，只是走到
        # F[i] = min(F[i-1] + cost[i-1], F[i-2] + cost[i-2])
        # 最终结果是 F[len(cost)] 即走过第 len(cost)-1 层

        # 上一个，上上一个
        lp, fp = 0, 0
        for i in range(2, len(cost)+1):
            fp, lp = lp, min(lp+cost[i-1], fp + cost[i-2])
        return lp

三、相似题目

这个题目有个相似题目：70. 爬楼梯：https://leetcode-cn.com/problems/climbing-stairs/

这个题目的动态规划方程是类似的，这里直接给出实现代码：

class Solution:
    def climbStairs(self, n: int) -> int:
        if not n:
            return 0

        if n < 2:
            return 1

        # F[i] 表示到第 i 阶台阶需要多少步子
        # F[i] = F[i-1] + F[i-2]

        F = [0] * (n + 1)
        F[1] = 1
        F[2] = 2

        for i in range(3, n+1):
            F[i] = F[i-1] + F[i-2]
        return F[-1]

同样也可以对空间做优化，这里就不实现了

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-12-21，如有侵权请联系 cloudcommunity@tencent.com 删除

对象存储