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

【动态规划篇】746.使用最小花费爬楼梯

在这里插入图片描述
在这里插入图片描述

746.使用最小花费爬楼梯

题目链接: 746.使用最小花费爬楼梯
题目叙述: 给你一个整数数组 cost ,其中 cost[i] 是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1:

输入: cost = [10,15,20]
输出: 15
解释: 你将从下标为 1 的台阶开始。

  • 支付 15 ,向上爬两个台阶,到达楼梯顶部。
    总花费为 15 。

示例 2:

输入: cost = [1,100,1,1,1,100,1,1,100,1]
输出: 6
解释: 你将从下标为 0 的台阶开始。

  • 支付 1 ,向上爬两个台阶,到达下标为 2 的台阶。
  • 支付 1 ,向上爬两个台阶,到达下标为 4 的台阶。
  • 支付 1 ,向上爬两个台阶,到达下标为 6 的台阶。
  • 支付 1 ,向上爬一个台阶,到达下标为 7 的台阶。
  • 支付 1 ,向上爬两个台阶,到达下标为 9 的台阶。
  • 支付 1 ,向上爬一个台阶,到达楼梯顶部。
    总花费为 6 。

提示:

2 <= cost.length <= 1000
0 <= cost[i] <= 999


解题思路:
解法一:

  1. 状态表示
    在这里插入图片描述
    dp[0] 表示爬到0位置的最小花费
    dp[1] 表示爬到1位置的最小花费
    dp[2] 表示爬到2位置的最小花费
    .
    .
    dp[i]表示爬到i位置的最小花费
  2. 状态转移方程
    i之前或之后的位置的状态,推导出dp[i]的值
    dp[i]表示到达i位置的最小花费
    要么到达i-1的位置一1步到达i位置,要么到达i-2的位置走两步到达i位置
    🍃根据最近的一步来划分问题
    在这里插入图片描述
    dp[i] = min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2])
  3. 初始化
    保证填表的时候不越界
    dp[0] = dp[1] = 0;
  4. 填表顺序
    从左往右
  5. 返回值
    dp[n]

代码实现:

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {//1.创建dp表int n = cost.size();vector<int> dp(n + 1);//2.初始化  由于vector的特性不写默认是0;for (int i = 2; i <= n; i++)//3.dp方程dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);return dp[n];//最后要爬到楼顶,所以要返回dp[n]}
};

时间复杂度:O(n)
空间复杂度:O(n)

解法二:

  1. 状态表示
    dp[i]表示:以i为起点到达楼顶时的最小花费
  2. 状态转移方程
    分为两种情况:
     ➀支付i位置的费用后,从i+1的位置到终点
     ➁支付i位置的费用后,从i+2的位置到终点
    在这里插入图片描述
    dp[i] = min(dp[i + 1] + cost[ i ],dp[i + 2] + cost[ i ])
  3. 初始化
    若从n-1位置出发到达楼顶只需支付n-1位置的费用
    若从n-2位置出发到达楼顶只需支付n-2位置的费用
    在这里插入图片描述
    仅需初始化最后两个位置
    dp[n-1] = cost[n-1],dp[n-2] = cost[n-2]
  4. 填表顺序
    从右往左
  5. 返回值
    min(dp[0],dp[1])

代码实现:

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {//1.初始化dp表//2.初始化//3.填表//4.返回结果int n = cost.size();vector<int> dp(n);dp[n - 1] = cost[n - 1];dp[n - 2] = cost[n - 2];for (int i = n - 3; i >= 0; i--){dp[i] = cost[i] + min(dp[i + 1], dp[i + 2]);}return min(dp[0], dp[1]);}
};

时间复杂度:O(n)
空间复杂度:O(n)


👍 如果对你有帮助,欢迎:

  • 点赞 ⭐️
  • 收藏 📌
  • 关注 🔔

相关文章:

【动态规划篇】746.使用最小花费爬楼梯

746.使用最小花费爬楼梯 题目链接&#xff1a; 746.使用最小花费爬楼梯 题目叙述&#xff1a; 给你一个整数数组 cost &#xff0c;其中 cost[i] 是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用&#xff0c;即可选择向上爬一个或者两个台阶。 你可以选择从下标为 …...

类和对象:

1. const运算符重载&#xff1a; 1. const成员函数&#xff1a; 我们来看我们的下面的代码&#xff1a; 我们来看这个&#xff0c;我们的对象使用const进行修饰&#xff0c;然后我们对象d1调用我们的成员函数&#xff0c;然后我们取d1的地址然后传过去&#xff0c;这时候我们的…...

研究整除的性质——最大公约数(GCD)和最小公倍数(LCM)

最大公约数&#xff08;GCD&#xff09;和最小公倍数&#xff08;Least Common Multiple&#xff0c;LCM&#xff09;研究整除的性质&#xff0c;非常古老&#xff0c;在2000多年前就得到了很好的研究。由于简单易懂&#xff0c;有较广泛的应用&#xff0c;它们是竞赛中频繁出现…...

jenkins 配置邮件问题整理

版本&#xff1a;Jenkins 2.492.1 插件&#xff1a; A.jenkins自带的&#xff0c; B.安装功能强大的插件 配置流程&#xff1a; 1. jenkins->系统配置->Jenkins Location 此处的”系统管理员邮件地址“&#xff0c;是配置之后发件人的email。 2.配置系统自带的邮件A…...

FastAPI复杂查询终极指南:告别if-else的现代化过滤架构

title: FastAPI复杂查询终极指南:告别if-else的现代化过滤架构 date: 2025/3/14 updated: 2025/3/14 author: cmdragon excerpt: 本文系统讲解FastAPI中复杂查询条件的构建方法,涵盖参数验证、动态过滤、安全防护等18个核心技术点。通过引入策略模式、声明式编程等技术,彻…...

MySQL行列转化

初始化表结构&#xff1a; CREATE TABLE student_scores (student_id int NOT NULL,student_name varchar(50) DEFAULT NULL,math_score int DEFAULT NULL,english_score int DEFAULT NULL,science_score int DEFAULT NULL,PRIMARY KEY (student_id) ) ENGINEInnoDB DEFAULT C…...

施磊老师c++(六)

继承与多态-多重继承 文章目录 继承与多态-多重继承1.虚基类和虚继承本节内容 2.菱形继承---怎么解决?本节内容**面试问题: 怎么理解多重继承的?**---重点 3.c提供的四种类型转换本节内容 1.虚基类和虚继承 本节内容 多重继承? 代码复用, 一个派生类 有多个基类 抽象类—有…...

c++:AVL树

1.概念 由于二叉搜索树不能确保为近似完全二叉树的结构&#xff0c;节点相同的情况下&#xff0c;高度可能会很高&#xff0c;高度有可能会很低&#xff0c;所以搜索次数不能稳定维持在logn级别。我们在二叉搜索树的基础上进行平衡调整就可以控制搜索次数稳定在logn级别。 而AV…...

HTML编辑MP4保存名称

上图是HTML的界面&#xff0c;需要点击EDIT_MP4的选项&#xff0c;然后就出现文本框输入MP4名称。输入对应的MP4文件名称后&#xff0c;则点击Add_MP4按钮就可以把MP4的名称修改到json文件里面&#xff0c;json文件是network_detail.json文件。 HTML和CGI程序的交互 上图是htm…...

以太坊AI代理与PoS升级点燃3月市场热情,2025年能否再创新高?

币热网深度报道&#xff1a;以太坊AI代理与PoS升级引爆3月热潮&#xff0c;2025年能否再攀历史新高&#xff1f; 原文来源&#xff1a;币热网 - 区块链信息资讯平台 以太坊升级&#xff0c;市场热情高涨 近期&#xff0c;以太坊市场犹如被一股神秘力量点燃&#xff0c;掀起了…...

IDEA2024又一坑:连接Docker服务连不上,提示:Cannot run program “docker“: CreateProcess error=2

为新电脑安装了IDEA2024版&#xff0c;因为局域网中安装有Docker,所以这台电脑上没有安装&#xff0c;当运行时发现死活连不上Docker报&#xff1a;Cannot run program “docker“: CreateProcess error2 分析&#xff1a; Docker服务有问题 其它电脑都能连&#xff0c;排除 网…...

css基本功

为什么 ::first-letter 是伪元素&#xff1f; ::first-letter 的作用是选择并样式化元素的第一个字母&#xff0c;它创建了一个虚拟的元素来包裹这个字母&#xff0c;因此属于伪元素。 grid布局 案例一 <!DOCTYPE html> <html lang"zh-CN"><head&…...

ALSA vs OSS:Linux 音频架构的演变与核心区别

在 Linux 音频系统的发展过程中&#xff0c;OSS&#xff08;Open Sound System&#xff09; 和 ALSA&#xff08;Advanced Linux Sound Architecture&#xff09; 曾分别在不同阶段承担着音频管理的角色。OSS 是 Linux 早期的音频架构&#xff0c;而 ALSA 作为其继任者&#xf…...

双指针算法介绍+算法练习(2025)

一、介绍双指针算法 双指针&#xff08;或称为双索引&#xff09;算法是一种高效的算法技巧&#xff0c;常用于处理数组或链表等线性数据结构。它通过使用两个指针来遍历数据&#xff0c;从而减少时间复杂度&#xff0c;避免使用嵌套循环。双指针算法在解决诸如查找、排序、去重…...

第八节:红黑树(初阶)

【本节要点】 红黑树概念红黑树性质红黑树结点定义红黑树结构红黑树插入操作的分析 一、红黑树的概念与性质 1.1 红黑树的概念 红黑树 &#xff0c;是一种 二叉搜索树 &#xff0c;但 在每个结点上增加一个存储位表示结点的颜色&#xff0c;可以是 Red和 Black 。 通过对 任何…...

【C++标准库类型】深入理解C++中的using声明:从基础到实践

目录 一、using声明基础 1.1 基本语法形式 1.2 典型应用场景 1.3 作用域规则 二、关键注意事项 2.1 命名冲突处理 2.2 头文件使用规范 2.3 与typedef的对比 三、面向对象中的应用 3.1. 解除派生类名称隐藏&#xff08;核心应用&#xff09; 3.2. 构造函数继承&#…...

蓝桥杯2024年第十五届省赛真题-回文数组

题目描述 小蓝在无聊时随机生成了一个长度为 n 的整数数组&#xff0c;数组中的第 i 个数为ai&#xff0c;他觉得随机生成的数组不太美观&#xff0c;想把它变成回文数组&#xff0c;也是就对于任意i ∈ [1, n] 满足 ai an−i1 。小蓝一次操作可以指定相邻的两个数&#xff0c…...

多数元素——面试经典150题(力扣)

题目 给定一个大小为 n 的数组 nums &#xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的&#xff0c;并且给定的数组总是存在多数元素。 示例 1&#xff1a; 输入&#xff1a;nums [3,2,3] 输出&#xff1a;3 …...

QT中委托QStyledItemDelegate的使用

目录 一、子类化委托 二、委托方法实现 1)createEditor 2)setEditorData 3)setModelData 4)updateEditorGeometry 三、委托使用 四、总结 Qt的数据容器控件采用模型/视图(model/view)架构设计。模型用于存放控件的数据,视图则用于显示编辑数据,而委托则是…...

android 调用wps打开文档并感知保存事件

需求场景 在项目开发中会碰到需要调用WPS打开Word,Excel,Ppt等Office系列文档的情况&#xff0c;网上目前少有正式介绍如何调用相关API打开文档&#xff0c;并实现文档编辑后回传给三方应用&#xff0c;本人在逛WPS社区时发现 解锁WPS二次开发新世界&#xff1a;Android开发用…...

前端 Webpack 面试题

1、什么是 Webpack?它有什么作用? Webpack 是一个前端资源打包工具,用于将 JavaScript、CSS、图片等项目资源进行模块化管理和打包。它能够将复杂的项目结构转化为浏览器友好的代码,提高前端项目的开发效率和性能。 模块打包:Webpack 将项目中的各个模块及依赖打包成一个…...

05延迟任务精准发布文章(redis实现延迟任务、分布式锁)

上架不代表发布(需要发布app端才会显示文章&#xff09; 1)文章定时发布 2)延迟任务概述 2.1)什么是延迟任务 定时任务&#xff1a;有固定周期的&#xff0c;有明确的触发时间 延迟队列&#xff1a;没有固定的开始时间&#xff0c;它常常是由一个事件触发的&#xff0c;而在…...

十六、从零搭建一个 Vue 3 后台管理系统:完整实战教程

Vue 3 作为当下最为流行的前端框架之一&#xff0c;凭借其简洁的 API 以及强大的性能&#xff0c;已然成为构建后台管理系统的首选工具。本文将一步一步地引导你从零开始搭建一个 Vue 3 后台管理系统&#xff0c;内容涵盖路由、权限管理、状态管理等核心功能&#xff0c;并且会…...

never_give_up

一个很有意思的题&#xff1a; never_give_up - Bugku CTF平台 注意到注释里面有1p.html&#xff0c;我们直接在源代码界面看&#xff0c;这样就不会跳转到它那个链接的&#xff1a; 然后解码可得&#xff1a; ";if(!$_GET[id]) {header(Location: hello.php?id1);exi…...

DeepSeek结合Mermaid绘图(流程图、时序图、类图、状态图、甘特图、饼图)转载

思维速览&#xff1a; 本文将详细介绍如何利用DeepSeek结合Mermaid语法绘制各类专业图表&#xff0c;帮助你提高工作效率和文档质量。 ▍DeepSeek入门使用请看&#xff1a;deepseek保姆级入门教程&#xff08;网页端使用 本地客户端部署 使用技巧&#xff09; DeepSeek官网…...

「基于大模型的智能客服系统」语义理解、上下文记忆与反馈机制设计

网罗开发 &#xff08;小红书、快手、视频号同名&#xff09; 大家好&#xff0c;我是 展菲&#xff0c;目前在上市企业从事人工智能项目研发管理工作&#xff0c;平时热衷于分享各种编程领域的软硬技能知识以及前沿技术&#xff0c;包括iOS、前端、Harmony OS、Java、Python等…...

【后端】【django】导出 API 文档的几种方法

在 Django 项目里&#xff0c;导出 API 文档是很常见的需求&#xff0c;一般可以借助第三方库来实现。 使用 drf-yasg 导出 Swagger/OpenAPI 格式文档 drf-yasg 是一个用于 Django REST framework 的工具&#xff0c;能够自动生成 Swagger 和 OpenAPI 格式的 API 文档。 步骤…...

【HarmonyOS Next之旅】DevEco Studio使用指南(二)

目录 1 -> 工程模板介绍 2 -> 创建一个新的工程 2.1 -> 创建和配置新工程 2.1.1 -> 创建HarmonyOS工程 2.2.2 -> 创建OpenHarmony工程 1 -> 工程模板介绍 DevEco Studio支持多种品类的应用/元服务开发&#xff0c;预置丰富的工程模板&#xff0c;可以根…...

鸿蒙Next开发与实战经验总结

文章目录 1. 鸿蒙Next概述与开发环境搭建1.1 鸿蒙Next的核心特性1.2 开发环境搭建与工具链安装步骤工具链 1.3 第一个鸿蒙Next应用代码示例流程图 2. 鸿蒙Next应用架构与设计模式2.1 应用架构解析2.2 常用设计模式2.3 组件化开发实践 3. UI开发与布局系统3.1 基础UI组件3.2 布局…...

uniapp实现 uview1 u-button的水波纹效果

说明&#xff1a; 由于uview2已经移除水波纹效果&#xff0c;这边又觉得那个效果好看&#xff0c;所以开发这个功能(原谅我不会录动图) 效果&#xff1a; 具体代码&#xff1a; <view class"ripple-container" touchstart"handleTouchStart" touchend&…...

Linux练级宝典->任务管理和守护进程

任务管理 进程组概念 每个进程除了进程ID以外&#xff0c;还有一个进程组&#xff0c;进程组就是一个或多个进程的集合 同一个进程组&#xff0c;代表着他们是共同作业的&#xff0c;可以接收同一个终端的各种信号&#xff0c;进程组也有其唯一的进程组号。还有一个组长进程&a…...

金融行业替换传统的FTP传输系统的必要性

在如今这个数字化飞速发展的时代&#xff0c;金融行业对于信息安全性和数据传输效率的要求简直高得离谱。可是呢&#xff0c;你可能想不到&#xff0c;很多金融机构竟然还在用传统的FTP&#xff08;文件传输协议&#xff09;来处理日常的数据交换。 FTP在过去几十年里确实是网络…...

C# backgroundworker类(后台线程)

概念 在C#程序中&#xff0c;经常会有一些耗时较长的CPU密集型运算&#xff0c;如果直接在 UI 线程执行这样的运算就会出现UI不响应的问题。解决这类问题的主要途径是使用多线程&#xff0c;启动一个后台线程&#xff0c;把运算操作放在这个后台线程中完成。但是原生接口的线程…...

OpenAI智能体初探:使用 OpenAI Responses API 在 PDF 中实现检索增强生成(RAG)

大家好,我是大 F,深耕AI算法十余年,互联网大厂技术岗。 知行合一,不写水文,喜欢可关注,分享AI算法干货、技术心得。 欢迎关注《大模型理论和实战》、《DeepSeek技术解析和实战》,一起探索技术的无限可能! 引子 在信息爆炸的时代,从大量 PDF 文档中快速准确地检索信息…...

SqlServer数据库报错紧急或可疑无法访问的修复过程,亲测有效。

当 SQL Server 数据库被标记为 SUSPECT 状态时&#xff0c;表示数据库可能由于事务日志损坏、数据文件丢失或其他严重问题而无法正常启动。以下是一个详细的恢复步骤&#xff0c;基于搜索结果中的信息和常见的最佳实践&#xff1a; 恢复步骤 1. 确认数据库状态 将database-n…...

12.31[net]review

复用&#xff08;Multiplexing&#xff09;的概念 定义&#xff1a;在传输层&#xff0c;复用是指多个应用进程可以使用同一个传输层协议&#xff08;如 TCP 或 UDP&#xff09;来发送数据。从应用层的角度看&#xff0c;不同的应用进程&#xff08;如网页浏览器、邮件客户端等…...

Redis超高并发分key实现

Redis扛并发的能力是非常强的&#xff0c;所以高并发场景下经常会使用Redis&#xff0c;但是Redis单分片的写入瓶颈在2w左右&#xff0c;读瓶颈在10w左右&#xff0c;如果在超高并发下即使是集群部署Redis&#xff0c;单分片的Redis也是有可能扛不住的&#xff0c;如下图所示&a…...

Houdini学习笔记

1. Houdini中一次只能显示一个物体 如果要都显示 需要 merge 节点 粉色的是 以参考显示 2.对任意一个节点按F1 可以弹出houdini官方文档 3. 恢复视角 Space H,居中 Space G 居中选中物体...

Ubuntu 22.04使用pigz多线程快速解压/压缩文件

最近搞项目&#xff0c;资料太大&#xff0c;解压时间太久&#xff0c;于是想办法解决。 开贴记录。 1.安装pigz sudo apt install pigz 2.解压资料 解压命令为 tar --use-compress-programpigz -xvpf ***.tar.gz 将最后的部分***.tar.gz换成你自己的文件即可 例如 ti…...

子数组问题——动态规划

个人主页&#xff1a;敲上瘾-CSDN博客 动态规划 基础dp&#xff1a;基础dp——动态规划-CSDN博客多状态dp&#xff1a;多状态dp——动态规划-CSDN博客 目录 一、解题技巧 二、最大子数组和 三、乘积最大子数组 四、最长湍流子数组 五、单词拆分 一、解题技巧 区分子数组&…...

汉桑科技IPO:潜藏两大风险 公众投资者权益或受损

冰山之所以危险&#xff0c;是因为只有八分之一在水面上。 ——语出小说家海明威。 引 言 野村证券提供的一份报告显示&#xff0c;2025年前两个月&#xff0c;我国出口同比增长仅有2.3%&#xff0c;与去年四季度9.9%的增长显著下滑。与此同时&#xff0c;从2月1日开始&a…...

【3DGS】SuperSplat本地运行+修改监听端口+导入ply模型+修剪模型+在线渲染3DGS网站推荐

SuperSplat官网代码&#xff1a;https://github.com/playcanvas/supersplat 本地安装和运行 Clone the repository: git clone https://github.com/playcanvas/supersplat.git cd supersplat Install dependencies: npm install Build SuperSplat and start a local web ser…...

整数与字节序列相互转换

以下函数是用于二进制编解码的核心工具函数&#xff0c;实现 32/64 位整数与字节流之间的高效转换。 操作逻辑&#xff1a;将整数的每个字节依次写入缓冲区&#xff0c;从最低有效字节到最高有效字节内存布局&#xff1a;假设 value0x12345678&#xff0c;地址由低到高依次是0…...

嵌入式软件测试的东方智慧:WinAMS工具的技术哲学与实践启示——一名汽车电子工程师的七年工具演进观察

引言&#xff1a;在丰田精益生产线上诞生的测试哲学 2017年参与某日系车企的ECU&#xff08;电子控制单元&#xff09;联合开发时&#xff0c;我第一次在名古屋工厂见到产线旁部署的WinAMS测试站。不同于欧美工具强调的“全流程覆盖”&#xff0c;这个诞生于日本制造业精益文化…...

卫星遥感赋能气象服务:精准预测,智享生活

卫星遥感技术作为现代气象服务的“千里眼”和“顺风耳”&#xff0c;正以前所未有的精度和效率&#xff0c;革新着我们对天气的观测、预报与应对方式。今天&#xff0c;就让我们一同探索卫星遥感在气象服务中的奇妙应用。 星图云开放平台&#xff1a;专业气象的智慧之选 高精度…...

多个nodejs版本切换使用教程

想要多个nodejs版本来回切换TOC 先卸载本地已安装的nodejs下载安装nvm ,下载地址&#xff1a;https://github.com/coreybutler/nvm-windows/releases打开链接后 &#xff0c;选择 nvm-setup.exe 安装&#xff0c;安装路径避免空格和中文&#xff08;如 D:\nvm&#xff09; 选择…...

Vue.js 3 的设计思路:从声明式UI到高效渲染机制

目录 一、声明式UI与虚拟DOM的灵活性 二、渲染器&#xff1a;虚拟DOM到真实DOM的桥梁 三、组件的本质与实现 四、编译与运行时的协同优化 五、性能与可维护性的权衡 总结 Vue.js 3 作为新一代前端框架&#xff0c;其设计理念在声明式UI描述、虚拟DOM优化、组件化架构…...

Python控制语句 ——break和continue

1.以下关于Python循环结构的描述中,错误的是() 。 A、break用来结束当前当次语句,但不跳出当前的循环体。 B、遍历循环中的遍历结构可以是字符串、文件、组合数据类型和range函数等。 C、Python通过for,while等保留字构建循环结构。 D、continue只结束本次循环。 答案:A。在…...

Linux websocket服务器、配网方法、QT客户端程序

一、linux websocket服务器 参考下面的代码编译和运行 websocket_for_linux: c语言实验websocket通信&#xff0c;含服务端和客户端示例代码 二、网络配置 Linux本地开启server和client&#xff0c;可正常通信。 换局域网另外一台PC后无法测试通过。 解决办法&#xff1a;…...

Python网络爬虫之requests库的使用方法

requests库是Python中用于发送HTTP请求的一个重要库,在实际应用中,它被广泛用于爬取网页数据、调用API接口等。本节将详细讲解requests库的使用流程,包括发送HTTP请求、携带请求参数、处理服务器响应以及错误处理,帮助读者掌握requests库的基本使用方法。 1. 使用requests库…...