【题解】NowCoder DP4 最小花费爬楼梯

server/2024/9/23 3:19:15/

题目来源:牛客

DP4 最小花费爬楼梯

题目描述:

给定一个整数数组 cost , 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用,下标从 0 开始。一旦你支付此费用,即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

数据范围:数组长度满足 1 ≤ n ≤ 105 ,数组中的值满足 1 ≤ costi ≤ 104

输入描述:

第一行输入一个正整数 n ,表示数组 cost 的长度。
第二行输入 n 个正整数,表示数组 cost 的值。

输出描述:

输出最低花费。

示例1

输入:3
    2 5 20
输出:5
说明:你将从下标为1的台阶开始,支付5 ,向上爬两个台阶,到达楼梯顶部。总花费为5 。

示例2

输入:10
    1 100 1 1 1 90 1 1 80 1
输出:6
说明:你将从下标为 0 的台阶开始。
    1.支付 1 ,向上爬两个台阶,到达下标为 2 的台阶。
    2.支付 1 ,向上爬两个台阶,到达下标为 4 的台阶。
    3.支付 1 ,向上爬两个台阶,到达下标为 6 的台阶。
    4.支付 1 ,向上爬一个台阶,到达下标为 7 的台阶。
    5.支付 1 ,向上爬两个台阶,到达下标为 9 的台阶。
    6.支付 1 ,向上爬一个台阶,到达楼梯顶部。
    总花费为 6 。

解析

这题很明显的属于动态规划的问题,难度比较简单,只要系统学过动态规划的基本就可以轻松秒杀这题。这题告诉我们,台阶的花费是从该台阶向上爬时的花费,到达该台阶是不需要花费的。我们通过示例可以知道,最后一个台阶并不是楼梯顶部,最后一个台阶上面一层才是。
在这里插入图片描述
动态规划最重要的两点就是,①状态表示。②状态转移方程。
其中,状态表示在绝大多数情况下,使 dp表 的每一项数据表示当前情况的最终结果即可。比如说在这一题,我们的 dp[i] 就是到达 i 位置的最小花费,只要令 i 为结果那项的话,dp[i] 就是最终答案。
状态转移方程每一题都不同,需要分析。在这题里面,题目告诉我们,爬楼梯只能每次爬一个台阶或者两个台阶,因此,任意一层台阶只跟上一层和上一层的上一层有关。第 i 层只能通过第 i-1 层或者第 i-2 层到达,且走花费最小的那条路。所以我们能够推算出:dp[i] 就是 dp[i - 1] + cost[i - 1] (选择走上一台阶走一步到达)与 dp[i - 2] + cost[i - 2] (选择走上一个台阶的上一个台阶走两步到达)之间的最小值。

代码实现

#include<iostream>
using namespace std;const int N = 1e5 + 10;
int dp[N], cost[N];
int n;int main()
{cin >> n;for (int i = 0; i < n; ++i){cin >> cost[i];}// 由于向上爬楼梯才有花费,而我们可以直接选择从 0 或 1 开始dp[0] = 0;// 则到达第 0 层和第 1 层是不需要花费的dp[1] = 0;for (int i = 2; i <= n; ++i){// 上一层或上一层的上一层之间的最小值作为新的最小值dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}// 第 n - 1 层是最后一层台阶,n 则是楼梯顶部cout << dp[n];return 0;
}

http://www.ppmy.cn/server/13914.html

相关文章

零基础 Chrome 扩展开发指南

听说Chrome插件开发的浪潮即将来袭&#xff0c;我得趁热给大家整理一波干货&#xff0c;免得跌跌撞撞。咱们一起高光时刻到来前做好准备吧&#xff01;&#x1f973; 来说说方向&#xff0c;我有个小主意&#xff1a;如何提升商家处理业务的效率&#xff08;比如在Amazon、Sho…

如何在 C# 中选择使用抽象类或接口?

概述&#xff1a;在错综复杂的 C# 编程领域中&#xff0c;在抽象类和接口之间做出选择的决定是一个微妙的过程&#xff0c;它塑造了软件的结构和行为。当开发人员努力设计健壮且可维护的系统时&#xff0c;问题出现了&#xff1a;如何在 C# 中选择抽象类或接口&#xff1f;这个…

车载测试逆向工具JADX的使用详解看这篇就够了

JADX是一款强大的Android逆向工具&#xff0c;主要用于反编译APK文件&#xff0c;帮助用户分析APK文件的源代码&#xff0c;查看其逻辑以及查找相关的敏感信息。以下是一些JADX的使用指南和使用案例&#xff1a; 使用指南 安装与打开&#xff1a;JADX支持Windows、Linux和Mac…

redis基于Stream类型实现消息队列,命令操作,术语概念,个人总结等

个人大白话总结 1 在Redis Stream中&#xff0c;即使消息被消费者确认&#xff08;acknowledged, ACK&#xff09;&#xff0c;消息也不会自动从Stream数据结构中删除。这与Kafka或RabbitMQ等传统消息队列系统的做法不同&#xff0c;在那些系统中&#xff0c;一旦消息被消费并…

Qt-控件篇

QPushbutton 1、设置按钮文本 pushButton->setText("按钮"); 2、获取按钮文本 pushButton->text(); 3、设置按钮的大小为特定值&#xff08;宽度和高度&#xff09; pushButton->setFixedSize(width,height); 4、设置按钮悬停时的工具提示文本。 pushButto…

废液收集系统物联网远程监控解决方案

废液收集系统物联网远程监控解决方案 在面对日益严峻的环保压力和严格的法律法规要求下&#xff0c;构建一套高效、智能的废液收集系统物联网远程监控解决方案显得尤为重要。该方案旨在通过深度融合物联网技术、云计算、大数据分析等先进手段&#xff0c;实现对废液收集系统的…

代码随想录三刷day46

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣035. 不相交的线二、力扣53. 最大子数组和三、力扣392. 判断子序列 前言 每次当初始化的时候&#xff0c;都要回顾一下dp[i][j]的定义&#xff0c;不要…

python实现爬虫例子2

网络爬虫是一个可以自动抓取互联网内容的程序。Python有很多库可以用来实现网络爬虫&#xff0c;其中最常用的是requests&#xff08;用于发送HTTP请求&#xff09;和BeautifulSoup&#xff08;用于解析HTML&#xff09;。 以下是一个简单的Python网络爬虫示例&#xff0c;该爬…