首页 > 试题广场 >

最小花费爬楼梯

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

热度指数：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 。

算法知识视频讲解

Python 3

JianYue

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param cost int整型一维数组 
# @return int整型
#
class Solution:
    def minCostClimbingStairs(self , cost: List[int]) -> int:
        length = len(cost)
        for i in range(2, length):
            pre_2 = cost[i-2]
            pre_1 = cost[i-1]
            if pre_1 > pre_2:
                cost[i] = cost[i] + pre_2
            else:
                cost[i] = cost[i] + pre_1
        if cost[length - 2] > cost[length - 1]:
            return cost[length - 1]
        else:
            return cost[length - 2]

发表于 2022-09-14 11:25:16 回复(0)

Python 3

蓝鲸与风

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param cost int整型一维数组 
# @return int整型
#
class Solution:
    def minCostClimbingStairs(self , cost: List[int]) -> int:
        # write code here
        n=len(cost)
        if n<=2:
            return min(cost)
        dp=[0]*n
        dp[0]=cost[0]
        dp[1]=cost[1]
        for i in range(2,n):
            dp[i]=min(cost[i]+dp[i-1],cost[i]+dp[i-2])
        return min(dp[-1],dp[-2])

发表于 2022-08-21 13:44:52 回复(0)

Python 3

准备回家种田的程序猿

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param cost int整型一维数组 
# @return int整型
#
class Solution:
    __slots__=()
    def minCostClimbingStairs(self , cost: List[int]) -> int:
        # write code here
        #动态规划：
        cost.append(0)
        dp=[0 for i in range(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 dp[-1]

发表于 2022-08-15 15:26:50 回复(0)

Python 3

lun__

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param cost int整型一维数组 
# @return int整型
#
class Solution:
    def minCostClimbingStairs(self , cost: List[int]) -> int:
        # write code here
        n = len(cost) 
        dp = [0] * n 
        dp[0] = cost[0] 
        dp[1] = cost[1] 
        for i in range(2, n): 
            dp[i] = min(dp[i-1], dp[i-2]) + cost[i] 
#         print(dp) 
        return min(dp[n-1], dp[n-2])

发表于 2022-07-23 10:23:23 回复(0)

Python 3

小牛-007

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# @param cost int整型一维数组 
# @return int整型
#
class Solution:
    def minCostClimbingStairs(self , cost: List[int]) -> int:
        # write code here
        '''
            假如原数组一共 n 个台阶。要最终达到 下标大于等于n时，才算爬到了楼顶
            n 可以由 n-1 爬一个台阶，达到 n，n-1 时最低花费 为 s1，则最终花费为 s1 + cost[n-1]
              也可以由 n-2 爬两个台阶，达到 n，n-2 时最低花费 为 s2，则最终花费为 s2 + cost[n-2]
            那么最终最小的则为 min(s1 + cost[n-1], s2 + cost[n-2])
        '''
        n = len(cost)
        s = [0] * (n + 1)
        for i in range(n+1):
            if i <= 1:
                s[i] = 0
            elif i == 2:
                if cost[1] < cost[0]:
                    s[i] = cost[1]
                else:
                    s[i] = cost[0]
            else:
#                 s[i] = min(s[i-1] + cost[i-1], s[i-2] + cost[i-2])
                s[i] = min(s[i-1] + cost[i-1], s[i-2] + cost[i-2])
        
        return s[-1]

发表于 2022-05-28 12:01:31 回复(0)

Python 3

Vivimore

动态规划
时间复杂度：O(n) 空间复杂度：O(n)

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

发表于 2022-05-21 10:51:37 回复(0)

Python 3

danspace

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

发表于 2022-04-24 14:49:06 回复(0)

Python 3

九日爱学习

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

发表于 2022-04-22 14:46:11 回复(0)

Python 3

我是赵同学

状态转换就OK了

class Solution:
    def minCostClimbingStairs(self , cost: List[int]) -> int:
        # write code here
        n=len(cost)
        if n==1:
            return cost[0]
        c0 = 0   #到第0层最小花销
        c1 = 0   #到第1层最小花销
        
        for i in range(2,n+1):  #要走出最后一个台阶,所以n+1
            c0,c1 = c1,min(c0+cost[i-2],c1+cost[i-1])
            
        return c1

发表于 2022-04-09 15:57:28 回复(0)

Python 3

牛客356358940号

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param cost int整型一维数组 
# @return int整型
#
class Solution:
    def minCostClimbingStairs(self , cost: List[int]) -> int:
        # write code here
        dp={}            #表示上到第几层台阶
        dp[0]=dp[1]=0    #初始化
        n=len(cost)      #获取台阶数量
        #判断到达第i层时，跨一层台阶还是两层台阶花费较少
        for i in range(2,n+1):
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
        return dp[n]

发表于 2022-04-07 11:15:22 回复(0)

Python 3

路痴喵

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param cost int整型一维数组 
# @return int整型
#
class Solution:
    def minCostClimbingStairs(self , cost: List[int]) -> int:
        # write code here
        n = len(cost)
        tmp = [i for i in range(n+1)]
        for j in range(n+1):
            if j == 0:
                tmp[j] = 0
            elif j == 1:
                tmp[j] = 0
            else:
                tmp[j] = min(tmp[j-1]+cost[j-1], tmp[j-2]+cost[j-2])
        return tmp[n]

发表于 2022-03-22 23:10:11 回复(0)

Python 3

牛客356981786号

class Solution:
def minCostClimbingStairs(self , cost: List[int]) -> int:
# write code here
length = len(cost)
if length == 1 or length ==0:
return 0
if length == 2:
return cost[0] if cost[0] < cost[1] else cost[1]
dp = {}
before = 0
end = 0
for i in range(2, length+1):
left = before + cost[i-2]
right = end + cost[i-1]
before = end
end = left if left <= right else right
return end

发表于 2022-03-17 00:52:18 回复(0)

Python 3

窓

class Solution:
    def minCostClimbingStairs(self , cost) :
        height=len(cost)
        dst=[float('inf')]*(height+1)
        dst[0],dst[1]=0,0
        for i in range(2,height+1):
            dst[i]=min(dst[i-2]+cost[i-2],dst[i-1]+cost[i-1])
        return dst[height]

发表于 2022-03-10 16:24:06 回复(0)

Python 3

Virtual~

# 动态规划题解

class Solution:
    def minCostClimbingStairs(self , cost: List[int]) -> int:
        # write code here
        coin = 0
        n = len(cost)
        
        # dp[i] 代表爬到这层需要耗费的最小值
        dp = [0] * n
        # 初始化dp数组
        dp[0] = cost[0]
        dp[1] = cost[1]
        for i in range(2, n):
            # 状态迁移方程
            dp[i] = cost[i] + min(dp[i-1], dp[i-2])
#         print("dp: ", dp)
        return min(dp[-1], dp[-2])

发表于 2022-03-02 21:21:32 回复(0)