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

Leetcode 746 使用最小花费爬楼梯

题意理解

        给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用

        一旦你支付此费用,即可选择向上爬一个或者两个台阶
        你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯

        目标:使用最小的花费到达楼梯顶部。

       

        爬到第零阶、第一阶的最小花费为0.因为可以选择第一阶或第零阶开始跳。

        爬到第二阶的花费:

                从第一阶爬一步,cost=15,爬至第二阶。

                从第零阶爬两步,cost=10,爬至第二阶

                则爬到第二阶的最小花费cost=10

        爬到第三阶的花费:

                从第二阶爬一步,cost=到第二阶最小花费+15=10+20=30

                从第一阶爬两步,   cost=15

                则爬到第三阶的最小花费cost=15

解题思路

        采用动态规划的题目进行分析:

        1.根据题目dp[i]表示到达第i阶的最小花费。

        2.递推公式:dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

        3.初始化: dp[0]=0 dp[1]=0

        4.确定遍历顺序:后面的状态总是由前面的状态确定,则遍历顺序总是从前往后的。

        5.打印数组 ,可以用于debug验证思路。

1.动态规划解题

public int minCostClimbingStairs(int[] cost) {//定义存储int[] dp=new int[cost.length+1];//初始化dp[0]=0;dp[1]=0;//遍历for(int i=2;i<=cost.length;i++){//递推公式dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[cost.length];}

2.存储压缩

 public int minCostClimbingStairs(int[] cost) {//定义存储//初始化int min=0,dp0=0,dp1=0;if(cost.length==0||cost.length==1) return 0;//遍历for(int i=2;i<=cost.length;i++){//递推公式min=Math.min(dp1+cost[i-1],dp0+cost[i-2]);dp0=dp1;dp1=min;}return min;}

3.分析

时间复杂度:O(n) 用来遍历台阶的时间

空间复杂度

        数组存储:O(n)

        数值存储:O(1)

n表示台阶数

相关文章:

Leetcode 746 使用最小花费爬楼梯

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

2023/12/21作业

思维导图 代码 .text .global _start _start: 灯1 gpio时钟使能 [4]->1 0x5000A28 LDR R0,0x50000A28 指定寄存器地址 LDR R1,[R0]将寄存器取出放到R1 ORR R1,R1,#(0x1<<4)将第四位设置为1 STR R1,[R0]读取R0寄存器到R1 PE…...

Python 数据类型 (2)

1 集合类型&#xff1a;一维数组的集合 List列表是一个有序且可变的集合。允许重复成员。 turple元组是一个有序且不可更改的集合。允许重复成员。 Set集合是一个无序且无索引的集合。没有重复的成员。 dict字典是一个有序*且可变的集合。没有重复的成员。 &#xff01;&#x…...

【教程】自动检测和安装Python脚本依赖的第三方库

转载请注明出处&#xff1a;小锋学长生活大爆炸[xfxuezhang.cn] 背景说明 对于新python环境&#xff0c;要运行某个脚本&#xff0c;可能需要安装很多库&#xff0c;一般可以通过提供的requirements.txt来自动安装。但如果没有这个txt&#xff0c;那就得手动一个一个安装&#…...

0开始配置Cartographer建图和导航定位

0开始配置Cartographer 日期&#xff1a;12-19 硬件&#xff1a;激光雷达IMU 小车的tf变换&#xff1a; 建图配置 lua文件配置&#xff1a;my_robot.lua include "map_builder.lua" include "trajectory_builder.lua"options {map_builder MAP_BUILDE…...

Python中使用SQLite数据库的方法2-2

3.3.2 创建表单及字段 通过“3.2 创建Cursor类的对象”中创建的Cursor类的对象cur创建表单及字段&#xff0c;代码如图5所示。 图5 创建表单及字段 从图5中可以看出&#xff0c;通过Cursor类的对象cur调用了Cursor类的execute()方法来执行SQL语句。该方法的参数即为要指定的S…...

零代码也能玩出花:Mugeda在H5设计中的魔法力量

文章目录 一、Mugeda零代码可视化H5设计工具简介二、Mugeda零代码可视化H5设计实战案例1. 注册并登录Mugeda账号2. 选择模板3. 编辑页面内容4. 添加动画效果5. 预览和发布 三、Mugeda零代码可视化H5设计的优势《Mugeda零代码可视化H5设计实战》内容简介作者简介目录前言/序言 随…...

分布式、CAP 和 BASE 理论

在计算机科学领域&#xff0c;分布式系统是一门极具挑战性的研究方向&#xff0c;也是互联网应用中必不可少的优化实践&#xff0c;而 CAP 理论和 BASE 理论则是分布式系统中的两个关键的概念。 什么是分布式系统 首先&#xff0c;让我们来谈谈分布式系统。你可以将分布式系统…...

django之drf框架(两个视图基类、5个扩展视图类、9个视图子类)

两个视图基类 APIView和GenericAPIView drf提供的最顶层的父类就是APIView&#xff0c;以后所有的类都继承自他 GenericAPIView继承自APIView&#xff0c;他里面封装了一些工能 基于APIViewModelSerializerResposne写5个接口 子路由&#xff1a;app01>>>urls.py …...

23种设计模式学习

设计模式的分类 总体来说设计模式分为三大类&#xff1a; 创建型模式&#xff0c;共五种&#xff1a;工厂方法模式、抽象工厂模式、单例模式、建造者模式、原型模式。 结构型模式&#xff0c;共七种&#xff1a;适配器模式、装饰器模式、代理模式、外观模式、桥接模式、组合…...

php 8.4 xdebug扩展编译安装方法

最新版php8.4 xdebug扩展只能通过编译方式安装, pecl是安装不了的, 编译方法如下 下载最新版xdebug git clone https://github.com/xdebug/xdebug.git 却换入xdebug目录执行编译安装xdebug cd xdebug phpize./configure --enable-xdebugmakemake install3. 配置启用xdebug 这…...

66biolinks v42.0.0 已注册 – 生物短链接、URL 缩短器、QR 码和 Web 工具 (SAAS) 源码

66biolinks v42.0.0&#xff1a;全能生物短链接与网络工具平台 一、开篇介绍 66biolinks v42.0.0是一款集生物链接、URL缩短器、二维码和网络工具于一体的综合性软件解决方案。作为社交生物链接平台的佼佼者&#xff0c;66biolinks提供了全方位的功能&#xff0c;旨在满足用户…...

《Vue2.X 进阶知识点》- 防 ElementUI Divider 分割线

前言 使用 el-divider 背景为白色是没问题的。 但当背景换成其它颜色&#xff0c;问题就出现了&#xff01;&#xff01; 仔细看原来是两层&#xff0c;默认背景色是白色。 想着把背景色改为透明应该能用&#xff0c;结果发现背面是一条实线&#xff0c;难怪要用白色遮挡…不符…...

【第十二课】KMP算法(acwing-831 / c++代码 / 思路 / 视频+博客讲解推荐)

目录 暴力做法 代码如下 KMP算法 不同的next求法-----视频讲解/博客推荐 视频推荐 博客推荐 课本上的方法- prefix的方法- 求next数组思路---next数组存放前缀表的方式 s和p匹配思路 代码如下 暴力做法 遍历s主串中每一个元素&#xff0c;如果该元素等于模板串p中…...

JSON 简介

JSON是什么&#xff1f;(了解) JSON&#xff08;JavaScript Object Notation&#xff09;是一种轻量级的数据交换格式&#xff0c;常用于Web应用程序之间的数据传输。 JSON格式是一种文本格式&#xff0c;用于描述数据的结构和内容。它由两种基本元素组成&#xff1a;键值对和…...

Impala4.x源码阅读笔记(三)——Impala如何管理Iceberg表元数据

前言 本文为笔者个人阅读Apache Impala源码时的笔记&#xff0c;仅代表我个人对代码的理解&#xff0c;个人水平有限&#xff0c;文章可能存在理解错误、遗漏或者过时之处。如果有任何错误或者有更好的见解&#xff0c;欢迎指正。 上一篇文章Impala4.x源码阅读笔记&#xff0…...

Ubuntu2204配置samba

0.前情说明 samba服务器主要是用来局域网共享文件的&#xff0c;如果想公网共享可能行不通&#xff0c;我已经踩坑一天了 所以说如果你想满足公网samba共享你就可以不要看下去了 1.参考连接 Ubuntu 安装 Samba 服务器_ubuntu安装samba服务器-CSDN博客 2.安装samba服务 sud…...

AVL树(超详解)

文章目录 前言AVL树的概念AVL树的实现定义AVL树insert 单旋左单旋右单旋左单旋代码右单旋代码 双旋左右双旋右左双旋 测试AVL树的性能 前言 AVL树是怎么来的呢&#xff1f; 我们知道搜索二叉树会存在退化问题&#xff0c;退化以后就变成单支或者接近单支。 它的效率就变成O(N)…...

禁止浏览器记住密码和自动填充 element-ui+vue

vue 根据element-ui 自定义密码输入框&#xff0c;防止浏览器 记住密码和自动填充 <template><divclass"el-password el-input":class"[size ? el-input-- size : , { is-disabled: disabled }]"><inputclass"el-input__inner"…...

K8s实战-init容器

概念&#xff1a; 初始化容器的概念 比如一个容器A依赖其他容器&#xff0c;可以为A设置多个 依赖容易A1&#xff0c;A2&#xff0c;A3 A1,A2,A3要按照顺序启动&#xff0c;A1没有启动启动起来的 话&#xff0c;A2,A3是不会启动的&#xff0c;直到所有的静态容器全 部启动完毕…...

BY8X01-16P Arduino音频模块驱动库深度解析

1. 项目概述BY8X01-16P-Arduino 是一款专为 Arduino 生态设计的轻量级、高兼容性音频模块控制库&#xff0c;面向 BY8001-16P 与 BY8301-16P&#xff08;文档中偶见笔误为 BY83001-16P&#xff09;双芯片平台。该库并非简单封装串口指令&#xff0c;而是以嵌入式系统工程视角重…...

G-Helper高效解决ROG游戏本散热与性能平衡难题

G-Helper高效解决ROG游戏本散热与性能平衡难题 【免费下载链接】g-helper Lightweight Armoury Crate alternative for Asus laptops. Control tool for ROG Zephyrus G14, G15, G16, M16, Flow X13, Flow X16, TUF, Strix, Scar and other models 项目地址: https://gitcode…...

【AI微实验】这就deepseek对音频处理的理解╮(╯▽╰)╭

【手把手】零基础用PythonLibrosa搞定古琴音高识别&#xff0c;附完整代码1. 为什么要用代码“听”古琴&#xff1f;——传统音乐数字化的第一关1.1 从“泠泠七弦上”到“0和1”&#xff1a;音乐信息检索的价值1.2 核心任务拆解&#xff1a;基频&#xff08;F0&#xff09;是什…...

YOLOv5在边缘设备上部署实战:从Jetson Nano到树莓派,实现实时路面障碍检测

YOLOv5边缘计算部署实战&#xff1a;从Jetson Nano到树莓派的高性能路面检测方案 当自动驾驶小车需要识别前方突然出现的石块&#xff0c;或是智慧路侧单元要实时监控道路异常时&#xff0c;边缘设备上的AI推理能力就成为关键。本文将带您深入探索如何将YOLOv5模型部署到Jetson…...

手机拍照为啥总感觉差点意思?聊聊藏在ISP里的那些‘魔法’算法(从RawNR到TNR)

手机拍照为啥总感觉差点意思&#xff1f;聊聊藏在ISP里的那些‘魔法’算法&#xff08;从RawNR到TNR&#xff09; 每次看到别人用同款手机拍出的大片&#xff0c;再看看自己相册里灰蒙蒙的夜景照&#xff0c;是不是总觉得少了点什么&#xff1f;这背后其实藏着一整套名为ISP&am…...

FSearch:极速文件搜索工具,让Linux文件查找告别等待

FSearch&#xff1a;极速文件搜索工具&#xff0c;让Linux文件查找告别等待 【免费下载链接】fsearch A fast file search utility for Unix-like systems based on GTK3 项目地址: https://gitcode.com/gh_mirrors/fs/fsearch 还在为Linux系统中查找文件而烦恼吗&#…...

Gradio项目快速公网演示:除了share=True,你还有这几种轻量级内网穿透方案

Gradio项目快速公网演示&#xff1a;5种轻量级内网穿透方案横向评测 当你开发了一个酷炫的机器学习模型演示&#xff0c;或是精心设计的数据可视化界面&#xff0c;最迫切的需求往往是如何快速分享给同事或客户。Gradio的shareTrue参数可能是大多数开发者首先想到的方案&#x…...

WebGLInput:重构Unity WebGL输入体验的革命性方案

WebGLInput&#xff1a;重构Unity WebGL输入体验的革命性方案 【免费下载链接】WebGLInput IME for Unity WebGL 项目地址: https://gitcode.com/gh_mirrors/we/WebGLInput 在Unity WebGL开发中&#xff0c;输入法支持一直是开发者面临的核心挑战之一。WebGLInput项目通…...

Python实战:两步移动搜索法(2SFCA)在医疗资源可达性分析中的应用

1. 什么是两步移动搜索法&#xff08;2SFCA&#xff09;&#xff1f; 第一次听说两步移动搜索法&#xff08;2SFCA&#xff09;时&#xff0c;我完全被这个专业名词唬住了。后来在实际项目中用了才发现&#xff0c;它其实就是个"找资源"的聪明算法。想象一下你住在一…...

FLUX.1-dev FP8量化模型:让AI绘画不再依赖高端显卡

FLUX.1-dev FP8量化模型&#xff1a;让AI绘画不再依赖高端显卡 【免费下载链接】flux1-dev 项目地址: https://ai.gitcode.com/hf_mirrors/Comfy-Org/flux1-dev 还在为显卡显存不足而无法体验最新AI绘画技术而烦恼吗&#xff1f;FLUX.1-dev FP8量化模型正是为你量身打造…...