首页 > 试题广场 >

最小花费爬楼梯

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

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

算法知识视频讲解

Swift

牛客343575257号

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    func minCostClimbingStairs ( _ cost: [Int]) -> Int {
        //思路：使用dp数组存储最小数，每次移动数组时， 比较i-1和i-2的大小
        var dp = [Int]()
        //因为0和1不需要花费钱，所以dp[0]和dp[1]为0
        dp.append(0)
        dp.append(0)
        //开始爬楼：楼顶为cost.count+1
        for i in 2...cost.count {
            let m = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
            dp.append(m)
        }
        return dp.last! //返回楼顶的花费
    }
}

发表于 2026-01-29 11:30:24 回复(0)

Swift

行云流水_BJ

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    func minCostClimbingStairs ( _ cost: [Int]) -> Int {
        guard cost.count > 1 else {
            return 0
        }

        // p[i]代表抵达下标为i的楼层最低花费
        var p: [Int] = Array(repeating: Int.max, count: cost.count + 1)
        p[0] = 0; p[1] = 0
        for i in 2 ... cost.count {
            p[i] = min(p[i - 1] + cost[i - 1], p[i - 2] + cost[i - 2])
        }
        return p.last ?? 0
    }
}

发表于 2023-08-14 14:36:42 回复(0)