首页 > 试题广场 >

最小花费爬楼梯

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

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

算法知识视频讲解

JavaScript Node

thinkerer

function minCostClimbingStairs( cost ) {
    // write code here
    const n = cost.length;
    let curr=0,prev=0;
    for(let i =2;i<=n;i++){
        let next = Math.min(curr+cost[i-1],prev+cost[i-2])
        prev=curr
        curr=next
    }
    return curr
}

发表于 2024-03-22 08:59:07 回复(0)

JavaScript Node

牛客534362463号

function minCostClimbingStairs( cost ) {
    // write code here
    const dp = [];
    dp[0] = 0; dp[1] = 0;
    for(let i = 2; i <= cost.length; i++) {
        dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
    }
    return dp[cost.length];
}

发表于 2022-12-06 22:07:53 回复(0)

JavaScript Node

萌萌94

function minCostClimbingStairs( cost ) {
// write code here
let p = 0, q = 0;
for (let i = 0; i < cost.length; i++) {
[p, q] = [q, Math.min(p, q) + cost[i]];
}
return Math.min(p, q);
}

发表于 2022-05-25 16:58:42 回复(0)