数据结构与算法之最小爬楼梯费用动态规划
继续上一道题目,在上一道题目的基础之上,我们来解决这一道爬楼梯最小费用题。
一.题目描述


二.思路(动态规划五部曲)
确定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)
大家可以发现这道题目相对于上一道题目又难了一点,但整体思路是一样的。
大家加油!
相关文章:
数据结构与算法之最小爬楼梯费用动态规划
继续上一道题目,在上一道题目的基础之上,我们来解决这一道爬楼梯最小费用题。一.题目描述二.思路(动态规划五部曲)确定dp数组以及下标的含义使用动态规划,就要有一个数组来记录状态,本题只需要一个一维数组dp[i]就可以了。dp[i]的…...
阿里云ACA认证如何获取?
获取阿里云ACA(Alibaba Cloud Certification Associate)认证,需要按照以下步骤进行操作: 注册阿里云账号。如果您还没有阿里云账号,请先注册一个账号。登录阿里云官网。登录后,进入阿里云认证中心。选择AC…...
【Python入门第十六天】Python If ... Else
Python 条件和 If 语句 Python 支持来自数学的常用逻辑条件: 等于:a b不等于:a ! b小于:a < b小于等于:a < b大于:a > b大于等于:a > b 这些条件能够以多种方式使用,…...
两数之和的解法
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案…...
领导催我优化SQL语句,我求助了ChatGPT。这是ChatGPT给出的建议,你们觉得靠谱吗
作为一个程序员,无论在面试还是工作中,优化SQL都是绕不过去的难题。 为啥?工作之后才会明白,随着公司的业务量增多,SQL的执行效率对程系统运行效率的影响逐渐增大,相对于改造代码,优化SQL语句是…...
ArcGIS手动分割矢量面要素从而划分为多个面部分的方式:Cut Polygons Tool
本文介绍在ArcGIS下属ArcMap软件中,通过“Cut Polygons Tool”工具,对一个面要素矢量图层加以手动分割,从而将其划分为指定形状的多个部分的方法。 对于一个面要素矢量文件,有时我们需要对其加以划分,通过手动勾勒新的…...
【LeetCode】剑指 Offer 13. 机器人的运动范围 p92 -- Java Version
题目链接:https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/ 1. 题目介绍(13. 机器人的运动范围) 地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动࿰…...
[oeasy]python0091_仙童公司_八叛逆_intel_8080_altair8800_牛郎星
编码进化 个人电脑 计算机 通过电话网络 进行连接 极客 利用技术 做一些有趣的尝试 极客文化 是 认真研究技术的 文化 计算机 不再是 高校和研究机构高墙里面的 神秘事物而是 生活中常见的 家用电器 ibm 蓝色巨人脚步沉重 dec 小型机不断蚕食低端市场甚至组成网络干掉大型机…...
crontab 执行脚本报错,手动执行脚本正常的解决方法
一、出现的问题 有一个守护脚本XXX.sh,需要使用oracle用户在linux上配置定时任务,每1分钟检查执行一次。但是发现该脚本使用oralce用户手动启动没问题,能正常把程序启动起来,而使用crontab并没有把程序启动起来。 二、排查分析问…...
扎心话题 | 设计院背后的潜规则你知道吗?
大家好,我是建模助手。 大家都知道,在过去的2022年经济是真难!以小编所在的广东为例,全年GDP增长仅1.9%。 这个数据足以呈现一个社会现象——不仅消费力咔咔下降,各行各业更有不同程度地嗝屁。这其中也包括一些设计院…...
【JavaEE初阶】第二节.多线程( 进阶篇 ) 锁的优化、JUC的常用类、线程安全的集合类
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、synchronized的优化操作 1.1 锁膨胀/锁升级 1.2 锁消除 1.3 锁粗化二、JUC 2.1 Callable接口 2.2 ReentrantLock类&…...
大数据核心技术是什么
大数据的核心层:数据采集层、数据存储与分析层、数据共享层、数据应用层,可能叫法有所不同本质上的角色都大同小异。 大数据的核心技术都包括什么? 1、数据采集 数据采集的任务就是把数据从各种数据源中采集和存储到数据存储上,…...
「TCG 规范解读」初识 TPM 2.0 库续一
可信计算组织(Ttrusted Computing Group,TCG)是一个非盈利的工业标准组织,它的宗旨是加强在相异计算机平台上的计算环境的安全性。TCG于2003年春成立,并采纳了由可信计算平台联盟(the Trusted Computing Platform Alli…...
task与function
task和function主要是有助于代码的可重用性,都可以在module-endmodule之外声明。 1.function 1.1.function逻辑的综合 function:一个只有1个wire型输出值、全是组合逻辑的函数,且函数名即输出信号名,小括号中按顺序例化输入信号。…...
Android 基础知识4-3.1 TextView(文本框)详解
一、前言 TextView就是一个显示文本标签的控件,就是用来显示文本。可以在代码或者 XML中设置字体,字体大小,字体颜色 ,字体样式 (加粗级斜体),文字截断(比如:只显示10个字…...
点击化学 PEG 试剂1858242-47-3,Propargyl丙炔基-PEG1-乙酸活性酯
Propargyl-PEG1-Acetic acid-NHS ester,丙炔基-聚乙二醇-乙酸琥珀酰亚胺酯,丙炔基-PEG1-乙酸活性酯,丙炔基-PEG1-乙酸-NHS 酯产品规格:1.CAS号:1858242-47-32.分子式:C9H9NO53.分子量:211.174.包…...
正则表达式是如何运作的?
在日常的开发工作当中,我们必不可免的会碰到需要使用正则的情况。 正则在很多时候通过不同的组合方式最后都可以达到既定的目标结果。比如我们有一个需要匹配的字符串: hello,我们可以通过 / .</p>/ 以及 / .?</p>/ 来匹配&…...
JVM参数GC线程数ParallelGCThreads设置
1. ParallelGCThreads参数含义JVM垃圾回收(GC)算法的两个优化标的:吞吐量和停顿时长。JVM会使用特定的GC收集线程,当GC开始的时候,GC线程会和业务线程抢占CPU时间,吞吐量定义为CPU用于业务线程的时间与CPU总消耗时间的比值。为了承…...
java 线程的那些事
什么是进程: 你把它理解成一个软件 什么是线程: 你把它理解成软件里面的一个功能,做的事情 什么是多线程: 你把它理解成 软件里面的某一个功能,原先是一个人累死累活的在那里完成,现在好了,多…...
如何利用 Python 进行客户分群分析(附源码)
每个电子商务数据分析师必须掌握的一项数据聚类技能 如果你是一名在电子商务公司工作的数据分析师,从客户数据中挖掘潜在价值,来提高客户留存率很可能就是你的工作任务之一。 然而,客户数据是巨大的,每个客户的行为都不一样。20…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...
MyBatis中关于缓存的理解
MyBatis缓存 MyBatis系统当中默认定义两级缓存:一级缓存、二级缓存 默认情况下,只有一级缓存开启(sqlSession级别的缓存)二级缓存需要手动开启配置,需要局域namespace级别的缓存 一级缓存(本地缓存&#…...
