首页 > 试题广场 >

最小花费爬楼梯

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

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

算法知识视频讲解

牛客题解官

发表于 2022-04-22 12:38:17

精华题解题目主要信息: 给定一个数组，其中每个元素代表该级楼梯向上爬需要支付的费用，下标从0开始一旦支付费用，可以任意选择爬一级或是二级需要求爬到顶楼，即越过数组末尾元素所需要的最小花费可以从下标为0或是1的台阶开始举一反三：学习完本题的思路你可以解决如下题目： BM62.斐波那契数列 BM6 展开全文

千禧1

发表于 2022-03-15 21:55:43

经典的DP分析 1、一般dp[i]就表示结果，那么i就表示下标。 2、这道题是要走出去，所以就是要走出去前前一步。 3、dp转移方程分析走到当前台阶是从哪一步，dp[i-1]和dp[i-2] 加上当前当前台阶的花费 import java.util.*; public class Solut 展开全文

fred-coder

发表于 2022-02-17 11:33:34

动态规划, 每次走的步骤取决于前两个的状态; 状态转移方程: 当长度 < 2 时,直接返回 cost[0]; 当长度 >= 2 时,当前值取决于min(dp[i-1], dp[i-2]) + cost[i]; 代码如下: class Solution: def minCostCl 展开全文

菜鸡孙连城

发表于 2022-03-24 19:22:28

dp dp 你看我长得像dp吗？刚抄了一道题，还是不太懂dp，dp难dp易，dp就是放狗屁，快点去下地可以用一个数组记录每次爬到第i阶楼梯的最小花费，然后每增加一级台阶就转移一次状态，最终得到结果每次到一个台阶，只有两种情况，要么是它前一级台阶向上一步，要么是它前两级的台阶向上两步，因为在前面展开全文

摸鱼学大师

发表于 2022-02-19 14:00:09

题目主要信息: 给定一个数组，其中每个元素代表该级楼梯向上爬需要支付的费用，下标从0开始一旦支付费用，可以任意选择爬一级或是二级需要求爬到顶楼，即越过数组末尾元素所需要的最小花费可以从下标为0或是1的台阶开始具体思路: 可以用一个数组记录每次爬到第i阶楼梯的最小花费，然后每增加一级台阶就展开全文

Double_冰

发表于 2022-05-12 16:55:55

/* 动态规划，d[n] = min(d[i-1]+cost[i-1],d[i-2]+cost[i-2]); */ int min(int a, int b){ if(a>b)&nbs 展开全文

风中的聂鲁达

发表于 2022-02-21 18:08:29

动态规划到达楼顶花费的最小值可以想成从楼顶往下2层或者从楼顶往下1层上来花费的最小值，由此递推，可设dp[i]为从第i楼往上走花费的最小值，则dp[i]的递推式为： dp[i]=min{dp[i−1],dp[i−2]}+cost[i]dp[i] = min \{ dp[i-1],dp[i-2]\} 展开全文