当前位置: 首页 > 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…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

Monorepo架构: Nx Cloud 扩展能力与缓存加速

借助 Nx Cloud 实现项目协同与加速构建 1 &#xff09; 缓存工作原理分析 在了解了本地缓存和远程缓存之后&#xff0c;我们来探究缓存是如何工作的。以计算文件的哈希串为例&#xff0c;若后续运行任务时文件哈希串未变&#xff0c;系统会直接使用对应的输出和制品文件。 2 …...