【DP】使用最小花费爬楼梯

题目

给你一个整数数组 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

题解

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

这段代码实现了一个动态规划算法来解决一个问题,即爬楼梯的最小花费问题。

算法的思路是,使用一个长度为 len(cost) 的列表 dp 来记录到达每个台阶所需的最小花费。其中 dp[i] 表示到达第 i 个台阶所需的最小花费。首先将 dp[0]dp[1] 初始化为对应台阶的花费,然后从第三个台阶开始,通过比较从前一个台阶和前两个台阶中选择花费较小的那个,并加上当前台阶的花费,更新 dp[i]

最后,返回到达最后一个台阶和倒数第二个台阶所需的最小花费中的较小值,即 min(dp[len(cost)-1], dp[len(cost)-2])

这个算法的时间复杂度为 O(n),其中 n 是台阶的数量。

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

© 版权声明
THE END
点赞10 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容