当前位置: 首页 > news >正文

数据结构与算法之最小爬楼梯费用动态规划

继续上一道题目,在上一道题目的基础之上,我们来解决这一道爬楼梯最小费用题。

一.题目描述

二.思路(动态规划五部曲)

  1. 确定dp数组以及下标的含义

使用动态规划,就要有一个数组来记录状态,本题只需要一个一维数组dp[i]就可以了。

dp[i]的定义:到达第i台阶所花费的最少体力为dp[i]

对于dp数组的定义,大家一定要清晰!

2.确定递推公式

可以有两个途径得到dp[i],一个是dp[i-1] 一个是dp[i-2]

dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。

dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢?

一定是选最小的,所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

3.dp数组如何初始化

看一下递归公式,dp[i]由dp[i - 1],dp[i - 2]推出,既然初始化所有的dp[i]是不可能的,那么只初始化dp[0]和dp[1]就够了,其他的最终都是dp[0]dp[1]推出。

那么 dp[0] 应该是多少呢? 根据dp数组的定义,到达第0台阶所花费的最小体力为dp[0],那么有同学可能想,那dp[0] 应该是 cost[0],例如 cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 的话,dp[0] 就是 cost[0] 应该是1。

4.确定遍历顺序

最后一步,递归公式有了,初始化有了,如何遍历呢?

因为是模拟台阶,而且dp[i]由dp[i-1]dp[i-2]推出,所以是从前到后遍历cost数组就可以了。

5.举例推导dp数组

拿示例2:cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ,来模拟一下dp数组的状态变化,如下:

如果大家代码写出来有问题,就把dp数组打印出来,看看和如上推导的是不是一样的。

以上分析完毕,整体C++代码如下:

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size() + 1);dp[0] = 0; // 默认第一步都是不花费体力的dp[1] = 0;for (int i = 2; i <= cost.size(); i++) {dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[cost.size()];}
};
  • 时间复杂度:O(n)

  • 空间复杂度:O(n)

大家可以发现这道题目相对于上一道题目又难了一点,但整体思路是一样的。

大家加油!

相关文章:

数据结构与算法之最小爬楼梯费用动态规划

继续上一道题目&#xff0c;在上一道题目的基础之上&#xff0c;我们来解决这一道爬楼梯最小费用题。一.题目描述二.思路(动态规划五部曲)确定dp数组以及下标的含义使用动态规划&#xff0c;就要有一个数组来记录状态&#xff0c;本题只需要一个一维数组dp[i]就可以了。dp[i]的…...

阿里云ACA认证如何获取?

获取阿里云ACA&#xff08;Alibaba Cloud Certification Associate&#xff09;认证&#xff0c;需要按照以下步骤进行操作&#xff1a; 注册阿里云账号。如果您还没有阿里云账号&#xff0c;请先注册一个账号。登录阿里云官网。登录后&#xff0c;进入阿里云认证中心。选择AC…...

【Python入门第十六天】Python If ... Else

Python 条件和 If 语句 Python 支持来自数学的常用逻辑条件&#xff1a; 等于&#xff1a;a b不等于&#xff1a;a ! b小于&#xff1a;a < b小于等于&#xff1a;a < b大于&#xff1a;a > b大于等于&#xff1a;a > b 这些条件能够以多种方式使用&#xff0c…...

两数之和的解法

给定一个整数数组 nums 和一个整数目标值 target&#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数&#xff0c;并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是&#xff0c;数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案…...

领导催我优化SQL语句,我求助了ChatGPT。这是ChatGPT给出的建议,你们觉得靠谱吗

作为一个程序员&#xff0c;无论在面试还是工作中&#xff0c;优化SQL都是绕不过去的难题。 为啥&#xff1f;工作之后才会明白&#xff0c;随着公司的业务量增多&#xff0c;SQL的执行效率对程系统运行效率的影响逐渐增大&#xff0c;相对于改造代码&#xff0c;优化SQL语句是…...

ArcGIS手动分割矢量面要素从而划分为多个面部分的方式:Cut Polygons Tool

本文介绍在ArcGIS下属ArcMap软件中&#xff0c;通过“Cut Polygons Tool”工具&#xff0c;对一个面要素矢量图层加以手动分割&#xff0c;从而将其划分为指定形状的多个部分的方法。 对于一个面要素矢量文件&#xff0c;有时我们需要对其加以划分&#xff0c;通过手动勾勒新的…...

【LeetCode】剑指 Offer 13. 机器人的运动范围 p92 -- Java Version

题目链接&#xff1a;https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/ 1. 题目介绍&#xff08;13. 机器人的运动范围&#xff09; 地上有一个m行n列的方格&#xff0c;从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动&#xff0…...

[oeasy]python0091_仙童公司_八叛逆_intel_8080_altair8800_牛郎星

编码进化 个人电脑 计算机 通过电话网络 进行连接 极客 利用技术 做一些有趣的尝试 极客文化 是 认真研究技术的 文化 计算机 不再是 高校和研究机构高墙里面的 神秘事物而是 生活中常见的 家用电器 ibm 蓝色巨人脚步沉重 dec 小型机不断蚕食低端市场甚至组成网络干掉大型机…...

crontab 执行脚本报错,手动执行脚本正常的解决方法

一、出现的问题 有一个守护脚本XXX.sh&#xff0c;需要使用oracle用户在linux上配置定时任务&#xff0c;每1分钟检查执行一次。但是发现该脚本使用oralce用户手动启动没问题&#xff0c;能正常把程序启动起来&#xff0c;而使用crontab并没有把程序启动起来。 二、排查分析问…...

扎心话题 | 设计院背后的潜规则你知道吗?

大家好&#xff0c;我是建模助手。 大家都知道&#xff0c;在过去的2022年经济是真难&#xff01;以小编所在的广东为例&#xff0c;全年GDP增长仅1.9%。 这个数据足以呈现一个社会现象——不仅消费力咔咔下降&#xff0c;各行各业更有不同程度地嗝屁。这其中也包括一些设计院…...

【JavaEE初阶】第二节.多线程( 进阶篇 ) 锁的优化、JUC的常用类、线程安全的集合类

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、synchronized的优化操作 1.1 锁膨胀/锁升级 1.2 锁消除 1.3 锁粗化二、JUC 2.1 Callable接口 2.2 ReentrantLock类&…...

大数据核心技术是什么

大数据的核心层&#xff1a;数据采集层、数据存储与分析层、数据共享层、数据应用层&#xff0c;可能叫法有所不同本质上的角色都大同小异。 大数据的核心技术都包括什么&#xff1f; 1、数据采集 数据采集的任务就是把数据从各种数据源中采集和存储到数据存储上&#xff0c…...

「TCG 规范解读」初识 TPM 2.0 库续一

可信计算组织&#xff08;Ttrusted Computing Group,TCG&#xff09;是一个非盈利的工业标准组织&#xff0c;它的宗旨是加强在相异计算机平台上的计算环境的安全性。TCG于2003年春成立&#xff0c;并采纳了由可信计算平台联盟&#xff08;the Trusted Computing Platform Alli…...

task与function

task和function主要是有助于代码的可重用性&#xff0c;都可以在module-endmodule之外声明。 1.function 1.1.function逻辑的综合 function&#xff1a;一个只有1个wire型输出值、全是组合逻辑的函数&#xff0c;且函数名即输出信号名&#xff0c;小括号中按顺序例化输入信号。…...

Android 基础知识4-3.1 TextView(文本框)详解

一、前言 TextView就是一个显示文本标签的控件&#xff0c;就是用来显示文本。可以在代码或者 XML中设置字体&#xff0c;字体大小&#xff0c;字体颜色 &#xff0c;字体样式 &#xff08;加粗级斜体&#xff09;&#xff0c;文字截断&#xff08;比如&#xff1a;只显示10个字…...

点击化学 PEG 试剂1858242-47-3,Propargyl丙炔基-PEG1-乙酸活性酯

Propargyl-PEG1-Acetic acid-NHS ester&#xff0c;丙炔基-聚乙二醇-乙酸琥珀酰亚胺酯&#xff0c;丙炔基-PEG1-乙酸活性酯&#xff0c;丙炔基-PEG1-乙酸-NHS 酯产品规格&#xff1a;1.CAS号&#xff1a;1858242-47-32.分子式&#xff1a;C9H9NO53.分子量&#xff1a;211.174.包…...

正则表达式是如何运作的?

在日常的开发工作当中&#xff0c;我们必不可免的会碰到需要使用正则的情况。 正则在很多时候通过不同的组合方式最后都可以达到既定的目标结果。比如我们有一个需要匹配的字符串&#xff1a; hello&#xff0c;我们可以通过 / .</p>/ 以及 / .?</p>/ 来匹配&…...

JVM参数GC线程数ParallelGCThreads设置

1. ParallelGCThreads参数含义JVM垃圾回收(GC)算法的两个优化标的&#xff1a;吞吐量和停顿时长。JVM会使用特定的GC收集线程&#xff0c;当GC开始的时候&#xff0c;GC线程会和业务线程抢占CPU时间&#xff0c;吞吐量定义为CPU用于业务线程的时间与CPU总消耗时间的比值。为了承…...

java 线程的那些事

什么是进程&#xff1a; 你把它理解成一个软件 什么是线程&#xff1a; 你把它理解成软件里面的一个功能&#xff0c;做的事情 什么是多线程&#xff1a; 你把它理解成 软件里面的某一个功能&#xff0c;原先是一个人累死累活的在那里完成&#xff0c;现在好了&#xff0c;多…...

如何利用 Python 进行客户分群分析(附源码)

每个电子商务数据分析师必须掌握的一项数据聚类技能 如果你是一名在电子商务公司工作的数据分析师&#xff0c;从客户数据中挖掘潜在价值&#xff0c;来提高客户留存率很可能就是你的工作任务之一。 然而&#xff0c;客户数据是巨大的&#xff0c;每个客户的行为都不一样。20…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...

BLEU评分:机器翻译质量评估的黄金标准

BLEU评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...