首页 > 试题广场 >

最小花费爬楼梯

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

热度指数：83609 时间限制：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 。

算法知识视频讲解

星空afsg

func minCostClimbingStairs( cost []int ) int {
    // write code here
    if len(cost) < 2 {
        return 0
    }
    //到前1个台阶所需花费和前2个台阶所需花费
    step_0_cost, step_1_cost := 0, 0
    for i := 2; i <= len(cost); i++ {
        step_0_cost,step_1_cost = step_1_cost, MinInt(step_0_cost + cost[i-2], step_1_cost + cost[i-1])
    }
    return step_1_cost
}

func MinInt(a int, b int) int {
    if a <= b {
        return a
    } else {
        return b
    }
}

发表于 2025-10-22 00:46:36 回复(0)

牛客918753804号

func minCostClimbingStairs( cost []int ) int {
    // write code here
    min := func(x, y int) int {
		if x < y {
			return x
		}
		return y
	}
	dp := make([]int, len(cost)+1)
	for i := 2; i <= len(cost); i++ {
		dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
	}
	return dp[len(cost)]
}

发表于 2024-09-28 23:19:25 回复(0)

秋叶原の黑猫

func minCostClimbingStairs( cost []int ) int {
    // write code here
    dp:=make([]int,len(cost))
    dp[0],dp[1]=cost[0],cost[1]
    for i:=2;i<len(cost);i++{
       dp[i]=min(dp[i-1],dp[i-2])+cost[i]
    }
    return min(dp[len(cost)-1],dp[len(cost)-2])
}
func min(a,b int)int{
    if a>b{
        return b
    }else{
        return a
    }
}

发表于 2022-06-12 20:58:33 回复(0)