使用最小花费爬楼梯 | 动态规划

1.使用最小花费爬楼梯

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

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。

2.题目解读在这里插入图片描述

例如上面的例子,从下标为0的地方开始爬楼梯,向上爬一个或者两个台阶,最后到达顶部,输出6。其实两个问题,就是我怎么知道从0下标还是1下标开始?我怎么知道是要爬一个还是两个台阶?

3.解决问题(解法一)

(1)、状态表示
上面的问题1,我怎么知道从0下标还是1下标开始?只需要定义dp[i]为到达 i 位置时的最⼩花费即可。 如:dp[3]根据以往的计算这个就是最小花费,至于从0还是1下标,那就要问,dp[0]和dp[1]的最小花费是多少。
(2)、状态转移⽅程
根据以往的推出的结果(dp[i]之前或之后),来推导dp[i]。这里根据题目推导状态转移方程,即可解决知道是要爬一个还是两个台阶(最优即:最小花费)。
在这里插入图片描述
(3)、初始化
dp[0] = dp[1] = 0本来就可以在0或1下标。
(4)、初始化顺序
这里根据题目要求,根据状态转移方程,从左往右,将dp填充。
(5)、返回值
返回dp[n]即为,返回结果。

4.参考代码(解法一)

C++版本:

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];}
};

Java版本:

class Solution {public int minCostClimbingStairs(int[] cost) {int n = cost.length;int dp[] = new int[n + 1];for(int i = 2;i <= n;i++){dp[i] = Math.min(cost[i - 1] + dp[i - 1],cost[i - 2] + dp[i -2]);}return dp[n];}
}
5.解决问题(解法二)

(1)、状态表示
dp[i]表示到达楼梯顶部的最少花费。
(2)、状态转移⽅程
在这里插入图片描述

(3)、初始化
dp[n -1] = cost[n-1],dp[n-2] = cost[n-2]
(4)、初始化顺序
这里根据题目要求,根据状态转移方程,从右往左,将dp填充。
(5)、返回值
返回min(dp[0],dp[i])就是结果

6.参考代码(解法二)

C++版本:

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp(n + 1);dp[n - 1] = cost[n - 1];dp[n - 2] = cost[n - 2];for(int i = n - 3;i >= 0;i--){dp[i] = min(cost[i] + dp[i + 1],cost[i] + dp[i + 2]);}return min(dp[0],dp[1]);}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/338690.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Spring系列-SpringMvc父子容器启动原理解析

1、Spring整合SpringMVC 特性&#xff1a; 说到Spring整合SpringMVC唯一的体现就是父子容器&#xff1a; 通常我们会设置父容器&#xff08;Spring&#xff09;管理Service、Dao层的Bean, 子容器(SpringMVC)管理Controller的Bean .子容器可以访问父容器的Bean, 父容器无法访…

【惯性传感器imu】—— WHEELTEC的惯导模块的imu的驱动安装配置和运行

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、IMU驱动安装1. 安装依赖2. 源码的下载3. 编译源码(1) 配置固定串口设备(2) 修改luanch文件(3) 编译 二、启动IMU1. 运行imu2. 查看imu数据 总结 前言 WHEE…

【C++进阶】深入STL之string:模拟实现走进C++字符串的世界

&#x1f4dd;个人主页&#x1f339;&#xff1a;Eternity._ ⏩收录专栏⏪&#xff1a;C “ 登神长阶 ” &#x1f921;往期回顾&#x1f921;&#xff1a;C模板入门 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; ❀STL之string &#x1f4d2;1. string…

图解 Python 编程(10) | 错误与异常处理

&#x1f31e;欢迎来到Python的世界 &#x1f308;博客主页&#xff1a;卿云阁 &#x1f48c;欢迎关注&#x1f389;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; &#x1f31f;本文由卿云阁原创&#xff01; &#x1f4c6;首发时间&#xff1a;&#x1f339;2024年6月2日&…

uni-app全局弹窗的实现方案

背景 为了解决uni-app 任意位置出现弹窗 解决方案 一、最初方案 受限于uni-app 调用组件需要每个页面都引入注册才可以使用&#xff0c;此方案繁琐&#xff0c;每个页面都要写侵入性比较强 二、改进方案 app端&#xff1a;新建一个页面进行跳转&#xff0c;可以实现伪弹窗…

认识微服务,认识Spring Cloud

1. 介绍 本博客探讨的内容如下所示 什么是微服务&#xff1f;什么是springcloud&#xff1f;微服务和springcloud有什么关系&#xff1f; 首先&#xff0c;没有在接触springcloud之前&#xff0c;我写的项目都是单体结构&#xff0c; 但随着网站的用户量越来越大&#xff0c;…

list的简单模拟实现

文章目录 目录 文章目录 前言 一、使用list时的注意事项 1.list不支持std库中的sort排序 2.去重操作 3.splice拼接 二、list的接口实现 1.源码中的节点 2.源码中的构造函数 3.哨兵位头节点 4.尾插和头插 5.迭代器* 5.1 迭代器中的operator和-- 5.2其他迭代器中的接口 5.3迭代器…

【TCP协议中104解析】wireshark抓取流量包工具,群殴协议解析基础

Tcp ,104 ,wireshark工具进行解析 IEC104 是用于监控和诊断工业控制网络的一种标准&#xff0c;而 Wireshark则是一款常用的网络协议分析工具&#xff0c;可以用干解析TEC104 报文。本文将介绍如何使用 Wireshark解析 IEC104报文&#xff0c;以及解析过 程中的注意事项。 一、安…

C语言-01_HelloWord

文章目录 1.C程序运行机制2.HelloWorld的剖析① main()② 函数体③ printf()④ 标准库、头文件 3.输出3.1 printf()标准格式3.2 占位符3.3 输出格式 1.C程序运行机制 过程1&#xff1a;编辑 编写C语言源程序代码&#xff0c;并已文件的形式存储到磁盘中。源程序文件以“.c”作…

dubbo复习:(19)dubbo 和spring整合(老古董)

一、服务端依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache.org/POM…

【Linux】Linux工具——gcc/g++

1.使用vim更改信用名单——sudo 我们这里来补充sudo的相关知识——添加信任白名单用户 使用sudo就必须将使用sudo的那个账号添加到信用名单里&#xff0c;而且啊&#xff0c;只有超级管理员才可以添加 信用名单在/etc/sudoers里 我们发现它的权限只是可读啊&#xff0c;所以…

cocos入门5:编辑器界面介绍

Cocos Creator是一款功能强大的跨平台游戏开发工具&#xff0c;其编辑器界面设计直观易用&#xff0c;提供了从资源管理、场景编辑到脚本编写等一站式解决方案。下面是对Cocos Creator编辑器界面的详细介绍&#xff1a; 一、界面布局 Cocos Creator编辑器界面通常包含以下几个…

渲染100为什么是高性价比网渲平台?渲染100邀请码1a12

市面上主流的网渲平台有很多&#xff0c;如渲染100、瑞云、炫云、渲云等&#xff0c;这些平台各有特色和优势&#xff0c;也都声称自己性价比高&#xff0c;以渲染100为例&#xff0c;我们来介绍下它的优势有哪些。 1、渲染100对新用户很友好&#xff0c;注册填邀请码1a12有3…

IDeal下的SpringBoot项目部署

一、首先找到自己的sql文件&#xff0c;没有就从数据库挪进来 二、在Maven下打包一下&#xff08;点击package&#xff09;&#xff0c;看到BUILD SUCCESS就是打包好了 三、将上面两个文件分别挪到 linux 中对应的文件&#xff0c;没有就创建一个&#xff08;我的是spring_blog…

常见算法(基本查找、二分查找、分块查找冒泡、选择、插入、快速排序和递归算法)

一、常见算法-01-基本、二分、插值和斐波那契查找 1、基本查找/顺序查找 需求1&#xff1a;定义一个方法利用基本查找&#xff0c;查询某个元素是否存在 数据如下&#xff1a;{131&#xff0c;127&#xff0c;147&#xff0c;81&#xff0c;103&#xff0c;23&#xff0c;7&am…

WordPress子比主题美化-首页动态的图片展示

WordPress子比主题首页动态的图片展示 WordPress子比主题首页添加动态的图片展示&#xff0c;其他程序也可以用&#xff0c;复制代码到相应位置即可&#xff0c;也可作为指定分类&#xff0c;重点内容等&#xff0c;可以适合各个场景&#xff0c;需要的自取。 图片展示: 教程…

Spring源码之BeanDefinition的加载

Spring源码之BeanFactory和BeanDefinition BeanFactory和BeanDefinitionBeanFactoryBeanDefinition源码分析创建AnnotationConfigApplicationContext对象注册配置类refresh方法 BeanFactory和BeanDefinition BeanFactory BeanFactory是Spring提供给外部访问容器的根接口&…

MVC和MVVM

MVC Model层&#xff1a;用于处理应用程序数据逻辑的部分&#xff0c;通常负责在数据库中存取数据 View&#xff08;视图&#xff09;处理数据显示的部分。通常视图是依据模型数据创建的 Controller&#xff08;控制器&#xff09;是处理用户交互的部分。通常控制器负责从视…

Yolov10笔记

一、前言 清华大学团队设计的Yolov10. 在这项工作中&#xff0c;我们主要从后处理和模型结构两方面进一步优化YOLO系列模型的性能和延迟平衡。我们首先为YOLO引入了端到端训练的一致双重分配&#xff0c;这在大大降低推理延迟的情况下保证了性能。此外&#xff0c;我们针对YOLO…

养生与健康|一起跟随林曦老师养个元气满满

暄桐是一间传统美学教育教室&#xff0c;创办于2011年&#xff0c;林曦是创办人和授课老师&#xff0c;教授以书法为主的传统文化和技艺&#xff0c;皆在以书法为起点&#xff0c;亲近中国传统之美&#xff0c;以实践和所得&#xff0c;滋养当下生活。    在暄桐教室的六阶…