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

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...