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

【Leetcode每日一题】 动态规划 - 使用最小花费爬楼梯(难度⭐)(41)

1. 题目解析

题目链接:746. 使用最小花费爬楼梯

这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。

2.算法原理

一、设定状态表

为了解决这个问题,我们首先要明确一个“状态表”。这个状态表其实就是一个记录表,用来记录到达每一层楼时的最小花费。

我们设定dp[i]为到达第i层楼时的最小花费。注意,这里的dp[i]只表示到达第i层时的花费,并不包括在第i层本身需要支付的费用。

二、考虑状态转移

接下来,我们要思考如何从一层楼到达另一层楼,并计算出最小花费。

  1. 从第i-1层上来:如果我们从第i-1层爬上来,那么到达第i层的总花费就是dp[i-1] + cost[i-1],其中cost[i-1]是第i-1层的费用。

  2. 从第i-2层上来:另一种可能的情况是我们从第i-2层直接跳到第i层(假设有这样的跳跃能力)。那么到达第i层的总花费就是dp[i-2] + cost[i-2]

我们需要比较这两种情况,选择花费更小的那种方式。

三、初始化状态

在开始计算之前,我们需要给状态表一个起点。显然,站在第一层或第二层是不需要花费的,所以dp[0] = dp[1] = 0

四、填表顺序

按照我们前面讨论的状态转移过程,我们需要从左往右依次计算每一层的最小花费,直到最后一层。

五、得出结果

最后,当我们填满整个状态表后,dp[n]就代表了到达最顶层的最小花费,这就是我们要求的答案。

3.代码编写

class Solution 
{
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp(n + 1);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];}
};

The Last

嗯,就是这样啦,文章到这里就结束啦,真心感谢你花时间来读。

觉得有点收获的话,不妨给我点个吧!

如果发现文章有啥漏洞或错误的地方,欢迎私信我或者在评论里提醒一声~ 

相关文章:

【Leetcode每日一题】 动态规划 - 使用最小花费爬楼梯(难度⭐)(41)

1. 题目解析 题目链接&#xff1a;746. 使用最小花费爬楼梯 这个问题的理解其实相当简单&#xff0c;只需看一下示例&#xff0c;基本就能明白其含义了。 2.算法原理 一、设定状态表 为了解决这个问题&#xff0c;我们首先要明确一个“状态表”。这个状态表其实就是一个记录…...

Springboot旅游管理系统设计与实现

** &#x1f345;点赞收藏关注 → 私信领取本源代码、数据库&#x1f345; 本人在Java毕业设计领域有多年的经验&#xff0c;陆续会更新更多优质的Java实战项目&#xff0c;希望你能有所收获&#xff0c;少走一些弯路。&#x1f345;关注我不迷路&#x1f345;** 一、研究背景…...

c++学习笔记(10)

1. 二分答案是一种常用的算法思想&#xff0c;用于解决一些需要枚举所有可能答案的问题。它的基本思想是将问题的答案范围缩小到一半&#xff0c;然后根据一定的条件判断&#xff0c;再将答案范围缩小到一半&#xff0c;直到找到正确的答案或者确定不存在正确答案为止。 下面…...

Visual Studio - 添加快捷键图标

Visual Studio - 添加快捷键图标 1. Text Editor Toolbar Options -> Add or Remove Buttons -> Customize2. Toolbars3. Commands -> Debug4. Add Command...References 1. Text Editor Toolbar Options -> Add or Remove Buttons -> Customize 2. Toolbars B…...

突破边界:Web3开启数字化社会的新纪元

引言 随着科技的不断进步和数字化社会的发展&#xff0c;Web3正逐渐成为了人们关注的焦点。作为新一代互联网的演进形态&#xff0c;Web3具有突破传统边界、实现去中心化的特点&#xff0c;被认为将开启数字化社会的新纪元。本文将深入探讨Web3的概念、特点、应用场景&#xf…...

docker仓库登录及配置insecure-registries的方法

docker仓库登录及配置insecure-registries的方法 这篇文章主要介绍了docker仓库登录配置insecure-registries的方法,docker客户端如果配置中添加了insecure-registary配置&#xff0c;就不需要在docker 客户端配置上对应证书&#xff0c;如果不配置要在/etc/docker/certs.d/目…...

Lambda函数与Selenium WebDriverWait类一起使用

Lambda函数是一种匿名函数&#xff0c;也称为内联函数或者lambda表达式。它们在Python中用于创建简短的、一次性的函数。Lambda函数通常用于在代码中传递函数作为参数&#xff0c;或者在需要一个简单的函数&#xff0c;但不想正式定义一个函数的情况下使用。 Lambda函数的特点…...

V R元宇宙平台的未来方向|V R主题馆加 盟|游戏体验馆

未来&#xff0c;VR元宇宙平台可能会呈现出以下发展趋势和可能性&#xff1a; 全面融合现实与虚拟世界&#xff1a; VR元宇宙平台将更加无缝地融合现实世界和虚拟世界&#xff0c;用户可以在虚拟环境中进行各种活动&#xff0c;与现实世界进行互动&#xff0c;并且体验到更加逼…...

sox命令用法

play input.wav 播放音频 sox input.wav -n stat 查看音频文件信息 soxi input.wav 查看音频文件信息input sox input.wav -n stat -v 不失真最大调整量 sox -v 0.8 input.wav output.wav 调整音量0.8,&#xff08;大于1为扩大&#xff0c;小于1为缩小&#xff09; sox *.wav *…...

Android kotlin全局悬浮窗全屏功能和锁屏页面全屏悬浮窗功能二

1.前言 在进行app应用开发中,在实现某些功能中要求实现悬浮窗功能,分为应用内悬浮窗 ,全局悬浮窗和 锁屏页面悬浮窗功能 等,接下来就来实现这些悬浮窗全屏功能,首选看下第二部分功能实现 2.kotlin实现锁屏页面悬浮窗全屏功能二分析 悬浮窗是属于Android系统的一种浮动窗…...

[数据结构]二叉树与递归OJ

上回我们手撕了一棵二叉树,并且通过递归完成了遍历,这回我们将深入理解用递归解决相关的二叉树问题,数量使用分治的思想. 上回的代码: #include<stdio.h> #include<stdlib.h> typedef struct BinTreeNode {struct BinTreeNode* left;struct BinTreeNode* right;i…...

vue iframe实现父页面实时调用子页面方法和内容,已解决

父页面标签添加鼠标按下事件 父页方法中建立iframe通信 实时调用子页面方法 实时更改子页面文本内容...

Spring Cloud Gateway教程

1 微服务网关概述 Spring Cloud Gateway是在 Spring 生态系统之上构建的API网关服务&#xff0c;旨在为微服务架构应用提供一种简单有效的统一的API路由管理方式。 Spring Cloud Gateway主要功能&#xff1a; 反向代理认证鉴权流量控制熔断日志监控 2 Spring Cloud Gateway三…...

解码新时代内存架构:探秘数据在内存中的灵动驻足

欢迎来到白刘的领域 Miracle_86.-CSDN博客 系列专栏 C语言知识 先赞后看&#xff0c;已成习惯 创作不易&#xff0c;多多支持&#xff01; 随着信息技术的飞速发展&#xff0c;我们身处一个数据爆炸的时代。数据的处理和存储方式正日益成为技术革新的重要领域。在新时代的…...

前端基础篇-前端工程化 Vue 项目开发流程(环境准备、Element 组件库、Vue 路由、项目打包部署)

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 环境准备 1.1 安装 NodeJs 1.2 验证 NodeJs 环境变量 1.3 配置 npm 的全局安装路径 1.4 切换 npm 的淘宝镜像( npm 使用国内淘宝镜像的方法(最新) ) 1.5 查看镜像…...

【通用人工智能AGI元年-各领域的精彩AI/LLM(持续更新)】

AI元年弄潮儿 通用人工智能AGI时代大模型LLM集成平台&#xff1a;Poe语言大模型&#xff1a;ChatGPT音乐&#xff1a;Suno文生图&#xff1a; [Stable Diffusion整合包](https://www.bilibili.com/video/BV1iM4y1y7oA/?spm_id_from333.999.0.0&vd_source260c69efcf1f56243…...

【微服务】设计弹性微服务架构模式

目录 模式#1 — 超时模式#2 — 重试模式#3— 隔离模式#4— 断路器模式#5 — 冗余推荐超级课程: Docker快速入门到精通Kubernetes入门到大师通关课AWS云服务快速入门实战在微服务架构中,服务通常相互协作以提供业务用例。这些服务可能在可用性、可伸缩性、弹性等方面具有…...

Websocket + Vue使用

这里有一篇文档可以参考一下> 闪现 POM文件 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId><version>2.7.0</version> </dependency> WebSocketConf…...

AI程序员革命:探析Devin的登场与编程未来

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…...

vue 控制窗口禁止缩放,已解决

注意&#xff1a;不是浏览器窗口禁止缩放 1.vue框架中&#xff0c;index.html文件head标签中加上内容 <meta name"viewport" content"widthdevice-width, initial-scale1, maximum-scale1, user-scalable0"><script>document.addEventListen…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...

前端中slice和splic的区别

1. slice slice 用于从数组中提取一部分元素&#xff0c;返回一个新的数组。 特点&#xff1a; 不修改原数组&#xff1a;slice 不会改变原数组&#xff0c;而是返回一个新的数组。提取数组的部分&#xff1a;slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...