首页 > 试题广场 >

最小代价爬楼梯

[编程题]最小代价爬楼梯
  • 热度指数：9114 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
你需要爬上一个 n 层的楼梯，在爬楼梯过程中， 每阶楼梯需花费非负代价，第i阶楼梯花费代价表示为 cost[i] ， 一旦你付出了代价，你可以在该阶基础上往上爬一阶或两阶。
你可以从第 0 阶或者 第 1 阶开始，请找到到达顶层的最小的代价是多少。
n 和 cost[i] 皆为整数

数据范围： ,

输入描述:
输入为一串半角逗号分割的整数，对应cost数组，例如

10,15,20


输出描述:
输出一个整数，表示花费的最小代价
示例1

输入

1,100,1,1,1,100,1,1,100,1

输出

6
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2020-06-04 15:43:22
精华题解 题目难度：二星 考察点：动态规划 方法：动态规划 1.分析： 这个题的本质其实和跳楼梯差不多的，只不过加了代价而已，那么假设跳n个台阶的代价为f(n)那么： 如果第n个台阶是由跳1阶而来的，那么代价就是f(n-1)+a[n] 如果第n个台阶是由跳2阶而来的，那么代价就是f(n-2) 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 诗云panther
发表于 2021-08-29 08:36:18
include include using namespace std;int main(){ vector<int> cost; int c; while(scanf("%d,", &c) > 0){ cost.push 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 诗悦网络内推_有问必答
发表于 2021-11-08 12:51:35
解题思路 通过第n个阶梯的花费为通过前两个阶梯中累计花费最小的那个并加上自身的花费，即cost(n) = min(cost(n-1), cost(n-2)) + cost 最终计算得出cost(last) = min(cost(last - 1), cost(last -2)) 代码 -spec m 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 laglangyue
发表于 2020-05-30 18:48:28
递归：超时长 动态规划 dp:dp[n]=min(dp[n-1]+cost[n-1],dp[n-2]+cost[n-2])值得注意的是本题是跳过第n阶，从n或者n-1到达 第n+1，所以sout(dp[n+1]) import java.util.Scanner; public class Mai 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 codewind
发表于 2020-05-26 14:24:40
import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); String[] v = 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客409434554号
发表于 2022-01-10 05:31:23
">using namespace std; int main() { vector<int> v;v.push_back(0); int t; while(cin>>t) { v.push_back(t); s 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 iOS工程师 动态规划 安卓工程师 快手 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 2019 Java工程师
上传者：小小
难度：
38条回答 8718浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最小代价爬楼梯

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号