LeetCode746使用最小花费爬楼梯

题目描述

  给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。

解析

  动态规划问题,第i级所花费的有两种情况,一个是通过前一级跳过当前级数上去,此时的花费就是上一级的最小花费。另一个是通过自身爬出去,此时的最小花费就是上一级的最小花费或者上上一级的最小话费中小的那一个加自身的花费。

public int minCostClimbingStairs(int[] cost) {// cost.length >= 2int[][] dip = new int[2][cost.length];dip[0][0] = 0; dip[0][1] = cost[0];dip[1][0] = cost[0]; dip[1][1] = cost[1];for(int i = 2; i < cost.length; i++) {dip[0][i] = dip[1][i - 1];  // 经过上一级dip[1][i] = Math.min(dip[1][i - 1], dip[1][i - 2]) + cost[i];  // 经过自己}return Math.min(dip[0][cost.length - 1], dip[1][cost.length - 1]);}

  优化空间,实际上只需要记录三个级别的花费即可。

public int minCostClimbingStairs(int[] cost) {int n = cost.length;if (n == 2) {return Math.min(cost[0], cost[1]);}// 只需要维护前两步的最小成本int first = cost[0];  // 上上级的最小花费int second = cost[1]; // 上一级的最小花费int current = 0;      // 当前级的最小花费for (int i = 2; i < n; i++) {current = Math.min(first, second) + cost[i];first = second;second = current;}// 返回最后倒数第二级中的最小值,因为可以从这两步结束return Math.min(first, second);
}

在这里插入图片描述

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

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

相关文章

JVM运行数据区-Java堆

Java堆 堆区&#xff08;Heap区&#xff09;是JVM运行时数据区占用内存最大的一块区域&#xff0c;每一个JVM进程只存在一个堆区&#xff0c;它在JVM启动时被创建&#xff0c;JVM规范中规定堆区可以是物理上不连续的内存&#xff0c;但必须是逻辑上连续的内存。 1、堆区是线程…

R语言探索与分析17-CPI的分析和研究

一、选题背景 CPI&#xff08;居民消费价格指数&#xff09;作为一个重要的宏观经济指标&#xff0c;扮演着评估通货膨胀和居民生活水平的关键角色。在湖北省这个经济活跃的地区&#xff0c;CPI的波动对于居民生活、企业经营以及政府宏观经济政策制定都具有重要的影响。因此&a…

【MATLAB】概述1

非 ~ 注释 % 定义 >> 数组 赋值 赋值&#xff1a;>> x1 函数 数组 x[x1,x2] 行向量&#xff08;&#xff0c;or ) x[x1;x2] 列向量 x. 转置等间隔向量 1-10 向量&#xff1a;>>xlinspace(1,10,10) 矩阵 矩阵&#xff1a;>>A[1,2,3;4,5,6;7,8,9] …

容器中运行ip addr提示bash: ip: command not found【笔记】

容器中运行ip addr提示bash: ip: command not found 原因没有安装ip命令。 rootdocker-desktop:/# ip addr bash: ip: command not found rootdocker-desktop:/# apt-get install -y iproute2

设计模式20——职责链模式

写文章的初心主要是用来帮助自己快速的回忆这个模式该怎么用&#xff0c;主要是下面的UML图可以起到大作用&#xff0c;在你学习过一遍以后可能会遗忘&#xff0c;忘记了不要紧&#xff0c;只要看一眼UML图就能想起来了。同时也请大家多多指教。 职责链模式&#xff08;Chain …

使用耳机,如何避免听力受损?

使用耳机&#xff0c;如何避免听力受损&#xff1f; 随着数字时代生活方式的改变&#xff0c;无线耳机近年来成为消费者智慧生活的新宠。不少人会在上班通勤的路上习惯性地戴上耳机&#xff0c;打开播客或聆听音乐。工作中戴上耳机视频会议。午休的时候戴上耳机看视频。但你知…

设计模式23——状态模式

写文章的初心主要是用来帮助自己快速的回忆这个模式该怎么用&#xff0c;主要是下面的UML图可以起到大作用&#xff0c;在你学习过一遍以后可能会遗忘&#xff0c;忘记了不要紧&#xff0c;只要看一眼UML图就能想起来了。同时也请大家多多指教。 状态模式&#xff08;State&am…

【场景题】如何排查CPU偏高的问题

为了解决CPU偏高的问题&#xff0c;我们首先看一下每一个进程的CPU占用情况&#xff0c;使用命令Top 可以看见是进程id为2266的进程里面的java程序&#xff0c;占用了CPU90%使用情况 所以我们需要找到是哪一个代码导致的这样的情况&#xff0c;由于代码是线程执行的&#xff…

Three.js 研究:4、创建设备底部旋转的科技感圆环

1、实现效果 2、PNG转SVG 2.1、原始物料 使用网站工具https://convertio.co/zh/png-svg/进行PNG转SVG 3、导入SVG至Blender 4、制作旋转动画 4.1、给圆环着色 4.2、修改圆环中心位置 4.3、让圆环旋转起来 参考一下文章 Three.js 研究&#xff1a;1、如何让物体动起来 Thre…

解决 DataGrip 2024.1.3 连接 Tdengine 时timestamp字段显示时区不正确问题

设置中找到该设置&#xff0c;将原来的设置 yyyy-MM-dd HH:mm:ss 修改为: yyyy-MM-dd HH:mm:ss.SSS z 即可。 注意&#xff1a;只能修改第一个,修改后提示错误&#xff0c;但是查询数据时能成功格式化时间&#xff0c;修改第二个不生效&#xff0c;可能是 bug 具体格式见: Date…

macOS上用Qt creator编译并跑shotcut

1 简介 Shotcut是一个开源的跨平台的视频编辑软件&#xff0c;支持WIN/MACOS/LINUX等平台&#xff0c;由于该项目的编译较为麻烦&#xff0c;踩坑几许&#xff0c;因此写此文章记录完整编译构建过程&#xff0c;后续按此法编译&#xff0c;可减少走弯路&#xff0c;提高生产力。…

软件质量保障——三、四

三、黑盒测试 1.黑盒测试概述 1.1 如何理解黑盒测试&#xff1f; 1.2 黑盒测试有什么特点&#xff1f; 1.3 如何实施黑盒测试&#xff1f; 2. 黑盒测试用例设计和生成方法&#xff08;这里还是要自己找题做&#xff09; 2.1 等价类划分法 步骤&#xff1a; 1.选择划分准…

亚信安慧AntDB数据库与华为数据存储完成兼容性互认证

迎接数智时代&#xff0c;供给核心科技。日前&#xff0c;湖南亚信安慧科技有限公司&#xff08;简称&#xff1a;亚信安慧&#xff09;与华为技术有限公司&#xff08;简称&#xff1a;华为&#xff09;&#xff0c;完成了AntDB数据库产品与OceanProtect备份一体机及Oceanstor…

python学习笔记-04

高级数据类型 一组按照顺序排列的值称为序列&#xff0c;python中存在三种内置的序列类型&#xff1a;字符串、列表和元组。序列可以支持索引和切片的操作&#xff0c;第一个索引值为0表示从左向右找&#xff0c;第一个索引值为负数表示从右找。 1.字符串操作 1.1 切片 切片…

目标检测数据集 - 智能零售柜商品检测数据集下载「包含VOC、COCO、YOLO三种格式」

数据集介绍&#xff1a;智能零售柜商品检测数据集&#xff0c;真实智能零售柜监控场景采集高质量商品图片数据&#xff0c;数据集含常见智能零售柜商品图片&#xff0c;包括罐装饮料类、袋装零食类等等。数据标注标签包含 113 个商品类别&#xff1b;适用实际项目应用&#xff…

云数融合与大数据技术在日常生活中的创新应用探索

前言 移动云模型服务产品在中国移动旗下主要包括云计算、大数据、人工智能等服务&#xff0c;它依托广泛的算力资源(4N31X)、丰富的网络接入资源和高品质云专网&#xff0c;实现算网端资源一站式开通&#xff0c;构建企业级一体化解决方案。 文章目录 前言云计算的日常应用智…

Kafka自定义分区器编写教程

1.创建java类MyPartitioner并实现Partitioner接口 点击灯泡选择实现方法&#xff0c;导入需要实现的抽象方法 2.实现方法 3.自定义分区器的使用 在自定义生产者消息发送时&#xff0c;属性配置上加入自定义分区器 properties.put(ProducerConfig.PARTITIONER_CLASS_CONFIG,&q…

蓝桥杯物联网竞赛_STM32L071_20_用printf将数据显示在OLED上

需求&#xff1a; 第十五届国赛确实有点变态&#xff0c;显示部分大概有6个所以需要大量将sprintf与OLED_ShowString配合使用才能显示相应格式的数据&#xff0c;所以我在想能不能简化一下这一部分直接用写好的printf语句将数据显示到显示屏上呢&#xff1f; 代码&#xff1a…

李廉洋:6.4黄金原油今日行情价格涨跌趋势分析及最新操作建议多空布局;

黄金消息面分析&#xff1a;全球债券周二上涨&#xff0c;呼应美债隔夜的涨势。美联储或早降息的押注增强了主权债务的吸引力。澳大利亚和新西兰10年期债券收益率下跌至少8个基点&#xff0c;先前数据显示&#xff0c;美国5月份工厂活动萎缩的速度加快。日本10年期债券收益率下…

数字塔问题

#include<iostream> using namespace std; //从下向上得到最优值 void dtower(int a[][100],int s[][100],int n) {for(int in; i>1; i--){for(int j1; j<i; j){if(in)s[i][j]a[i][j];else{int ts[i1][j];if(t<s[i1][j1])ts[i1][j1];s[i][j]a[i][j]t;}}} } void…