首页 > 试题广场 >

最小花费爬楼梯

[编程题]最小花费爬楼梯

热度指数：58961 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

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

数据范围：数组长度满足 $1 \le n \le 10^5 \$ ，数组中的值满足 $1 \le cost_i \le 10^4 \$

示例1

输入

[2,5,20]

输出

说明

你将从下标为1的台阶开始，支付5 ，向上爬两个台阶，到达楼梯顶部。总花费为5

示例2

输入

[1,100,1,1,1,90,1,1,80,1]

输出

说明

你将从下标为 0 的台阶开始。
1.支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
2.支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
3.支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
4.支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
5.支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
6.支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

算法知识视频讲解

Python3

lintoon

class Solution:

def minCostClimbingStairs(self , cost: List[int]) -> int:

# write code here

nn=len(cost)

dp=[0*i for i in range(nn+1)]

dp[1]=cost[0]

dp[2]=min(cost[0],cost[1])

dp[3]=min(cost[1],cost[0]+cost[2])

for n in range(4,nn+1):

dp[n]=min(dp[n-2]+cost[n-2],dp[n-1]+cost[n-1])

return dp[nn]

编辑于 2024-04-15 17:16:16 回复(0)

Python3

LeoAlan

# 解法一
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        # 初始化一个dp数组，数组的值为走到这一步所需的花费，数组的长度为n+1，因为最终要走出去
        dp = [0] * (n + 1)
        # 从第一步开始走，所以dp[0]和dp[1]都为0，因为不需要花费，所以从第二步开始，所以从下标2开始遍历，到n+1结束
        for i in range(2, n + 1):
            # 当前花费为（从上一步走来的花费加上之前的花费）或者（从上上一步走来的花费加上之前的花费），取最小值
            dp[i] = min(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2])

        return dp[-1]


# 解法二
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        # 初始化一个dp数组，数组的值为走到这一步所需的再加上走出这一步所需的总花费
        dp = [0] * n

        dp[0:2] = cost[0:2]

        for i in range(2, n):
            dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])

        # 最后一步可以选择从倒数第一步走出去，或者从倒数第二步走出去，取最小值
        return min(dp[-1], dp[-2])

发表于 2023-10-14 18:12:21 回复(0)

Python3

你的大鲨鱼

原来是顶层，其实差不多，题目很***。

'''
class Solution:
    def minCostClimbingStairs(self , cost):
        num = len(cost)
        dp =[]
        dp.append(0)
        dp.append(0)
        if num ==3:
           return min(dp[0] + cost[0]+cost[2], dp[1]+cost[1])
        for i in range(2,num):
            if i ==num-1:
                dp.append(min(dp[i - 2] + cost[i - 2]+cost[i], dp[i - 1]+cost[i - 1]))       
            else:
                dp.append(min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]))
        
        return(dp[num-1])
'''

#改进就是层数加+1 ，不需要讨论3的临界问题
class Solution:
    def minCostClimbingStairs(self , cost):
        num = len(cost)
        dp =[]
        dp.append(0)
        dp.append(0)
        for i in range(2,num+1):
                dp.append(min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]))
        
        return(dp[num])

发表于 2023-09-21 10:41:56 回复(0)

Python3

牛客692053893号

Python 3，动态规划解法

class Solution:
    def minCostClimbingStairs(self , cost: List[int]) -> int:
        # write code here
        
        # 动态规划
        # 1、确定状态
        # 最后一步前必定是在第i-1级台阶 或 第i-2级台阶
        # 原问题：求通过第i级台阶所花费的最少代价
        # 子问题：求通过第i-1级台阶和通过第i-2级台阶之间花费的最少代价
        # 2、转移方程
        # f(i) = min {f(i-1)+cost(i-1), f(i-2)+cost(i-2)}
        # 3、初始条件
        # 因为可以选择直接从台阶0或台阶1开始爬楼梯，所以: f(0)=0, f(1)=0
        # 4、计算顺序
        # 从小到大依次计算
        # 5、编程实现
        n = len(cost)    # 有n级台阶
        f = [0]*(n+1)    # 台阶从0开始，所以索引n为楼梯顶部，即有n+1级台阶
        for i in range(2, n+1): # 按从小到大的顺序计算
            f[i] = min(f[i-1]+cost[i-1], f[i-2]+cost[i-2])
        return f[n]

发表于 2022-08-26 22:48:37 回复(0)