leetcode746.使用最小花费爬楼梯(动态规划)

news/2024/5/20 20:24:33

问题描述:

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

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

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

示例一:
 

输入:cost = [10,15,20]
输出:15
解释:你将从下标为 1 的台阶开始。
- 支付 15 ,向上爬两个台阶,到达楼梯顶部。
总花费为 15 

示例二:

输入:cost = [1,100,1,1,1,100,1,1,100,1]
输出:6
解释:你将从下标为 0 的台阶开始。
- 支付 1 ,向上爬两个台阶,到达下标为 2 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 4 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 6 的台阶。
- 支付 1 ,向上爬一个台阶,到达下标为 7 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 9 的台阶。
- 支付 1 ,向上爬一个台阶,到达楼梯顶部。
总花费为 6 。

问题解决:

方法一:

1.状态表示:

因为要使用动态规划来解决,所以必须要有dp数组来记录一个状态。

这道题中dp[i]表示到达i位置的最小花费,下面就要用前面的dp值以及cost值来表示dp[i]

2.状态转移方程

主要是通过之前的状态,来表示dp[i]的值。

因为题干中规定可以选择向上爬一个台阶或者两个台阶,对应dp[i]就要找出这两种情况下花费最小

的从而赋值给dp[i]。

dp[i]可以选择前一个台阶即[i - 1]的位置然后向上走一步,这时的花费为dp[i - 1] + cost[i - 1],对应的

为走一步的情况。

dp[i]可以选择前两个台阶即[i - 2]的位置然后向前走两步,这是的花费位dp[i - 2] + cost[i - 2],对应为

向前走两步的情况。

所以dp[i]的状态转移方程为:min(dp[i - 1] + cost[i - 1] , dp[i - 2] + cost[i - 2]).

3.初始化一些值

这一步主要是为了在填写dp表的时候不越界。

从状态转移方程中我们可以看到,使用了dp[i - 1]和dp[i - 2]这两个值,这也就意味着

我们需要初始化dp[0]和dp[1]这两个位置,那么应该初始化成什么呢?

因为题干中说可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯,所以这也就代表了前往第0个梯

子和第一个梯子不需要任何花费,所以初始化:

dp[0] = dp[i] = 0;

4.填表的顺序

应为dp[i]的实现依靠于dp[i - 1]和dp[i - 2]所以也就注定了顺序是从左向右的。

5.返回值

题干要求返回到达楼顶的最高位置,所以直接返回最高位置的dp数组的值就可以了。

细节:

到底哪里才算爬到楼顶,应该是将最后一个阶梯走完之后,才算爬到楼顶,所以也就注定了dp数组

的长度比cost数组的长度要多一位,用来记录最后到楼顶的花费。

对应的代码:

int minCostClimbingStairs(vector<int>& cost) 
{// dp[i] 表示到达i位置的最小花费int n = cost.size();vector<int> dp(n + 1);dp[0] = 0;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]);}return dp[n];
}

动态规划的代码的书写方式很固定,首先判断是否有特殊情况,有的话直接先进行判断,然后

1.创建dp表

2.初始化dp中的一些元素

3.顺序填表(状态转移方程)

4.返回 

方法二:

1.状态表示:

因为要使用动态规划来解决,所以必须要有dp数组来记录一个状态。

这道题中dp[i]表示从i位置出发,到达楼顶的最小花费

2.状态转移方程

主要是通过之后的状态,来表示dp[i]的值。

这里的dp[i]有了不同的含义,因为题干中规定可以向前走一步或者两步,所以可以选择后一个或者

后两个来取出最小的花费

dp[i]如果选择后一个台阶来进行跳跃,就需要从后一个位置出发,到达楼顶的最小花费来加上自己

位置本身的花费来表示dp[i]的值。

dp[i]如果选择后两个台阶来进行跳跃,就需要从后两个位置出发,到达楼顶的最小花费来加上自己

位置本身的画法来表示dp[i]的值。

所以dp[i]的状态转移方程是:dp[i] = min(dp[i + 1] + cost[i], dp[i + 2] + cost[i]).

3.初始化一些值

这一步主要是为了在填写dp表的时候不越界。

观察状态转移方程发现需要dp的后两个位置的值,这也就意味着我们要初始化

dp[n - 1]和dp[n - 2]这两个值,那么这两个值应该初始化成什么呢?

由题干可知:可选择向上爬一个或者两个台阶,所以只要这两个台阶的人支付自己所在的台阶的费

用,就可以实现到达顶端。

对dp[n - 1]和dp[n - 2]的初始化为:

dp[n - 1] = cost[n - 1],dp[n - 2] = cost[n - 2].

4.填表的顺序

可以从状态转移方程看出,填表顺序是从右到左的

5.返回值

应为题干规定可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯

所以dp[0]和dp[1]都有可能是最终的答案,谁小取谁

min(dp[0],dp[]1)

最终的代码如下:

class Solution 
{
public:int minCostClimbingStairs(vector<int>& cost) {// dp[i]表示从i位置出发,到达楼顶的最小花费//1.创建dp表int n = cost.size();vector<int> dp(n);//2.初始化dp中的一些元素dp[n - 1] = cost[n - 1];dp[n - 2] = cost[n - 2];//3.顺序填表(状态转移方程)for (int i = n - 3; i >= 0; i--) {dp[i] = min(dp[i + 1] + cost[i], dp[i + 2] + cost[i]);}//4.返回return min(dp[0], dp[1]);}
};

 这就是这道题的两种解法。


http://www.mrgr.cn/p/82847548

相关文章

继承介绍、经典类和新式类、继承和抽象、封装和派生、组合

【一】继承介绍继承是一种创建新类的方式,新建的类可以继承一个或多个父类(python支持多继承),父类又可称为基类或超类,新建的类称为派生类或子类。子类会“遗传”父类的属性,从而解决代码重用问题(去掉冗余的代码)继承:单继承:继承一个父类的子类 多继承:继承多个父…

【比邻智选】MR880A模组

&#x1f680;高性价比&#xff0c;5G/4G双模&#xff0c;稳定可靠 &#x1f310;功能丰富&#xff0c;5G特性一应俱全 &#x1f9e9;多封装兼容&#xff0c;适配性强&#xff0c;灵活升级智能设备

CH57x/CH58X/CH59X/CH32F/V208OTA使用说明

目前提供了两种OTA升级方式, 方式一:带库升级;每次升级可以带着库一起进行升级(带库升级适用于flash较大的芯片) 方式二:固定库升级;升级时库不会随着升级而升级(适用于flash不够用时) 方式一: 升级时需要同时烧录这三个固件:(可以使用isp工具同时烧录也可以使用合并…

JAVA二叉树相关习题5

1. 二叉树前序非递归遍历实现 。 . - 力扣&#xff08;LeetCode&#xff09; 递归的实现 public List<TreeNode> preOrder1(TreeNode root){List<TreeNode> retnew ArrayList<>();if(root null)return ret;ret.add(root);List<TreeNode> leftTree …

Calendar 366 II for Mac v2.15.5激活版:智能日历管理软件

在繁忙的工作和生活中&#xff0c;如何高效管理日程成为了许多人的难题。Calendar 366 II for Mac&#xff0c;作为一款全方位的日历管理软件&#xff0c;以其独特的功能和优秀的用户体验&#xff0c;成为您的日程好帮手。 Calendar 366 II for Mac支持多种视图模式&#xff0c…

loons2024年05月09日20:04:57

1 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 1

远动通讯屏的作用

远动通讯屏的作用 远动通讯屏有时有称为调度数据网柜&#xff0c;远动通讯屏具体干啥作用&#xff1f;远动通讯屏是以计算机为基础的生产过程与调度自动化系统&#xff0c;可以对现场的运行设备进行监视和控制、以实现数据采集、设备测量、参数调节以及各类信号报警等各项功能。…

从零开始!学习绘制3D表情的详细指南

在2020 年的苹果全球开发者大会(WWDC)&#xff0c;苹果发布了新的 macOS 11(又名 Big Sur)。其中在UI视觉方面macOS Big Sur 系统最大的变化就是图标上&#xff0c; Big Sur更新了很多新设计风格的 3D应用图标&#xff0c;3D设计的确可以提升UI整体的视觉氛围&#xff0c;并且现…

邮件的发送

邮件发送和接收的协议 SMTP协议 (Simple Mail Transfer Protocol)属于TCP/IP协议族。 控制信件的中转方式,帮助每台计算机在发送或中转信件时找到下一个目的地。 SMTP服务器是遵循SMTP协议的发送邮件服务器。POP3协议 (Post Office Protocol - Version 3)属于TCP/IP协议族。…

P3842 [TJOI2007] 线段

https://img2024.cnblogs.com/blog/3335712/202405/3335712-20240509201346814-526640377.png洛谷-题目链接 [TJOI2007] 线段 提示 我们选择的路线是(1, 1) (1, 6)(2, 6) (2, 3)(3, 3) (3, 1)(4, 1) (4, 2)(5, 2) (5, 6)(6, 6) (6, 4) (6, 6)不难计算得到,路程的总长度是 24。…

力扣-21. 合并两个有序链表-js实现

/*** Definition for singly-linked list.* function ListNode(val, next) {* this.val (valundefined ? 0 : val)* this.next (nextundefined ? null : next)* }*/ /*** param {ListNode} list1* param {ListNode} list2* return {ListNode}*/ const mergeTwoList…

【linux学习指南】linux 环境搭建

文章目录 &#x1f4dd;前言&#x1f320; 云服务器的选择&#x1f320;阿里云&#x1f320;腾讯云&#x1f320;华为云 &#x1f320;使用 XShell 远程登陆到 Linux&#x1f309;下载 XShell &#x1f320;查看 Linux 主机 ip&#x1f309; XShell 下的复制粘贴&#x1f309; …

2024中国植物资源化妆品创新展在国家植物园成功举办

2024中国植物资源化妆品创新展&#xff08;简称国植美妆展&#xff09;于今年05月06日在北京国家植物园圆满落下帷幕。国植美妆展由中国广告协会化妆品工作委员会与中国抗衰老促进会化妆品产业分会指导&#xff0c;北京华晟德观文化科技发展有限公司主办&#xff0c;于03月30日…

ssh、PAM模块

.ssh/known_hosts 存储ssh指纹 sshd 服务器端 /etc/ssh/sshd_config 服务器端的配置文件 man 5 sshd_config 服务器端的配置文件帮助 echo root:1111|chapasswd 修改密码 openssl rand -base 64 9 随机取9位密码(随机数经过base编码取9位) ssh常用参数: Port 22 #生产建…

敏捷冲刺day2--数字工匠队

这个作业属于哪个课程 软件工程这个作业的要求是什么 项目冲刺这个作业的目标 冲刺日志2站立式会议照片工作困难 有部分知识不知道,要额外学习 昨日完成工作 用户登录前面前端初版 今日计划工作 登录界面前后端处理 项目燃尽图每日总结 陈家谦:继续学习 陆靖:继续努力 代码签…

Android C++ 开发调试 LLDB 工具的使用

文章目录 调试环境准备基础命令Breakpoint CommandsWatchpoint CommandsExamining VariablesEvaluating ExpressionsExamining Thread StateExecutable and Shared Library Query Commands 参考&#xff1a; Android 中在进行 NDK 开发的时候&#xff0c;我们经常需要进行 C 代…

CloudXR:更高效便捷的XR应用交互方案

CloudXR是一种新颖而先进的技术,旨在将虚拟现实和增强现实体验从本地设备转移到云端,主要功能也包括了远程渲染、流媒体传输、低延迟、高带宽和高质量的音视频传输。云化XR可以将高保真度的虚拟现实或增强现实场景实时传输到终端设备上,用户只需通过互联网即可感受到身临其境…

原来spring也可以AI

最近大模型是相当的火&#xff0c;尤其是在自然语言处理&#xff08;NLP&#xff09;、图像识别、语音识别等领域的应用&#xff0c;那对于工程同学来说应该如何接住这波破天的富贵呢&#xff1f; 想啥来啥&#xff0c;前段时间LangChain给我们整了一套钢铁战甲&#xff0c;让…

Kafk设计篇01(设计动机+持久化)

背景 本篇文章基于最新版本&#xff1a;kafka 3.7&#xff0c;其他版本的设计&#xff0c;请参考官网&#xff1a; https://kafka.apache.org/documentation/设计动机 任何组件都有它存在的必要&#xff0c;必然是要解决某一类问题的。我们来看看kafka设计的初衷如何。 kaf…