Day29 | 动态规划 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯
语言
Java
509. 斐波那契数
斐波那契数
题目
斐波那契数 (通常用 F(n)
表示)形成的序列称为 斐波那契数列 。该数列由 0
和 1
开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n > 1
给定 n
,请计算 F(n)
。
思路
动态规划五部曲
1.明白dp数组下标的含义
2.初始化
3.确定递推公式,有时候初始化要跟着递推公式来。
4.确定遍历顺序
5.举例推导dp数组
代码
标准版
class Solution {public int fib(int n) {//动规五部曲if (n < 2) return n;int[] dp = new int[n + 1];//明白dp数组下标含义dp[0] = 0;//初始化dp[1] = 1;for (int i = 2; i <= n; i++) {//确定遍历顺序dp[i] = dp[i -1] + dp[i - 2];//递推公式}return dp[n];//举例推导递推数组}
}
精简版
class Solution {public int fib(int n) {if (n < 2) return n;int a = 0;int b = 1;int c = 0;for (int i = 2; i <= n; i++) {c = a + b; a = b;b = c;}return c;}
}
易错点
数组定义大小的时候是n + 1因为索引从零开始。
遍历的时候从2开始从n结束。
70. 爬楼梯
爬楼梯
题目
假设你正在爬楼梯。需要 n
阶你才能到达楼顶。
每次你可以爬 1
或 2
个台阶。你有多少种不同的方法可以爬到楼顶呢?
思路
动规五部曲
数组dp[i]代表的含义,代表第i阶的时候有dp[i]种方法。
初始化:将0和1索引位置都设为1这样2的时候才有两种方法。
递推公式:从前面两次方法数相加,就是本次方法的数量。
遍历顺序:从前到后
举例推导dp数组。
代码
class Solution {public int climbStairs(int n) {int[] dp = new int[n + 1];dp[0] = 1;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}
易错点
索引为0的时候数值为1.
746. 使用最小花费爬楼梯
使用最小花费爬楼梯
题目
给你一个整数数组 cost
,其中 cost[i]
是从楼梯第 i
个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0
或下标为 1
的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
思路
动规五部曲
dp数组i位置的含义:在索引为I时花费最少的钱。
递推公式:目前索引花费最少的钱等于,前一个索引花费最少的钱和前一个索引带来带来的消耗,与前面第二索引带来的进行比较,取最少的。文字可能有点晦涩难懂,具体看代码。
初始值:因为在0或1的位置都不动,只有跳了才有消耗所以是0.
遍历:正序遍历
推导dp数组:用IDEA打印出来看看与结果有什么不同,发现错误就进行debug
代码
class Solution {public int minCostClimbingStairs(int[] cost) {int len = cost.length;int[] dp = new int[len + 1];dp[0] = 0;dp[1] = 0;for (int i = 2; i <= len; i++) {dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[len];}
}
易错点
明白递推公式的含义。
总结
今天是动态规划的第一天,继续加油,不断完善自己。
锲而不舍,金石可镂
相关文章:

Day29 | 动态规划 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯
语言 Java 509. 斐波那契数 斐波那契数 题目 斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) 0,F(1) 1 F(n) F(n -…...
【开源移植】MultiButton_小型按键驱动模块移植
MultiButton 简介 MultiButton 是一个小巧简单易用的事件驱动型按键驱动模块,可无限量扩展按键,按键事件的回调异步处理方式可以简化你的程序结构,去除冗余的按键处理硬编码,让你的按键业务逻辑更清晰。 使用方法 1.先申请一个…...

【Python系列】Python 字典合并
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

C# 设计模式之装饰器模式
总目录 前言 装饰器模式的主要作用就是扩展一个类的功能,或给一个类添加多个变化的情况。学习面向对象的都知道,如果想单纯的给某个类增加一些功能,可以直接继承该类生成一个子类就可以。应对一些简单的业务场景继承也就够了,但是…...

【uniapp离线打包】(基于Android studio)
文章目录 uniapp打包官方教程入口一、准备工作(工具三大件)Android Studio版本推荐 二、准备工作(Android壳和uniapp包)导入Android壳生成uniapp包将uniapp包导入android壳降低jdk版本 三、准备工作(证书)准备Android平台离线签名…...

稳稳的年化10%,多任务时序动量策略——基于pytorch的深度学习策略(附python代码)
原创文章第608篇,专注“AI量化投资、世界运行的规律、个人成长与财富自由"。 做因子挖掘这段时间,有一个观感。 传统的因子挖掘,尤其是手工构造因子,到遗传算法因子挖掘。——本身也是一种”拟合“,或者说试图”…...

C++分析AVL树
目录 AVL树介绍 AVL树平衡因子更新分析 AVL树插入时旋转与平衡因子更新 左单旋 右单旋 左右单旋 右左单旋 AVL旋转可行性 AVL树节点删除(待补充) AVL树分析 AVL树介绍 二叉搜索树在某些极端情况下可能会退化,为了解决这个问题&…...

aurora8b10b ip的使用(framing接口下的数据回环测试)
文章目录 一、Aurora8B/10B协议二、时钟、复位与状态指示1、时钟2、复位3、状态指示 三、数据发送、接受接口(1)AXI4-Stream位排序(2)Streaming接口(3)Framing接口(帧传输接口) 四、…...
如何通过OpenCV判断图片是否包含在视频内?
要判断图片是否包含在视频内,可以使用计算机视觉技术和图像处理方法。这通常涉及特征匹配或模板匹配。以下是一个基于OpenCV的解决方案,通过特征匹配的方法来实现这一目标。 步骤概述 读取视频和图片: 使用OpenCV读取视频文件和图片文件。 …...

大数据基础:Spark重要知识汇总
文章目录 Spark重要知识汇总 一、Spark 是什么 二、Spark 四大特点 三、Spark框架模块介绍 3.1、Spark Core的RDD详解 3.1.1、什么是RDD 3.1.2、RDD是怎么理解的 四、Spark 运行模式 4.1、Spark本地模式介绍 4.2、Spark集群模式 Standalone 4.3、Spark集群模式 Stan…...

Executable Code Actions Elicit Better LLM Agents
Executable Code Actions Elicit Better LLM Agents Github: https://github.com/xingyaoww/code-act 一、动机 大语言模型展现出很强的推理能力。但是现如今大模型作为Agent的时候,在执行Action时依然还是通过text-based(文本模态)后者JSO…...

循环结构(三)——do-while语句
目录 🍁引言 🍁一、语句格式 🚀格式1 🚀格式2 🍁二、语句执行过程 🍁三、实例 🚀【例1】 🚀【例2】 🚀【例3】 🍁总结 🍁备注 &am…...
pandas 或筛选
pandas 或筛选 在Pandas中,可以使用DataFrame.loc方法结合逻辑运算符来实现或筛选。这里提供一个简单的例子: import pandas as pd 创建示例DataFrame df pd.DataFrame({ ‘A’: [1, 2, 3, 4], ‘B’: [5, 6, 7, 8], ‘C’: [9, 10, 11, 12] }) 设定…...

工具(1)—截屏和贴图工具snipaste
演示和写代码文档的时候,总是需要用到截图。在之前的流程里面,一般是打开WX或者QQ,找到截图工具。但是尴尬的是,有时候,微信没登录,而你这个时候就在写文档。为了截个图,还需要启动微信…...

【从零开始一步步学习VSOA开发】快速体验SylixOS
快速体验SylixOS 安装完毕RealEvo-IDE 后,同时也安装了RealEvo-Simulator。RealEvo-Simulator 是一个虚拟运行环境,可以模拟各种体系结构并在其上运行 SylixOS。相比于物理板卡,在 RealEvo-Simulator 进行运行调测更加的方便快捷且成本低廉。…...
Ansible自动化:简化IT基础设施管理的艺术
目录 一.前言 二.Ansible简介 2.1什么是Ansible? 2.2Ansible的主要特点 2.3Ansible的应用场景 三.探索Ansible的高级功能 3.1 高级Playbook特性 3.2 Ansible Vault 3.3 动态Inventory 3.4Ansible Tower(AWX) 3.5模块开发 3.6 Ans…...
【Rust光年纪】探索Rust语言中的WebSocket库和框架:优劣一览
Rust语言中的实时通信利器:WebSocket库与框架全面解析 前言 随着Rust语言的不断发展,其在Web开发领域也变得越来越受欢迎。WebSocket作为实现实时通信的重要技术,在Rust的生态系统中也有多个库和框架提供了支持。本文将介绍几个主流的Rust …...

HTML 基础结构
目录 1. 文档声明 2. 根标签 3. 头部元素 4. 主题元素 5. 注释 6. 演示 1. 文档声明 <!DOCTYPE html>:声明文档类型,表示该文档是 html 文档, 2. 根标签 (1)所有的其他标签都要放在一对根标签中&#…...
多页合同怎么盖骑缝章_电子合同怎么盖骑缝章?
多页合同怎么盖骑缝章?电子合同怎么盖骑缝章? 对于纸质多页合同,盖骑缝章是一种常见的做法,用于确保合同的完整性,防止任何页面被替换或篡改。以下是盖骑缝章的基本步骤: 将所有合同页面平铺在桌面上。用…...

GD 32 IIC通信协议
前言: ... 通信方式 通信方式分为串行通信和并行通信。常见的串口就是串行通信的方式 常用的串行通信接口 常用的串行通信方式有USART,IIC,USB,CAN总线 同步与异步 同步通信:IIC是同步通信,有两个线一个是时钟信号线,一个数数据…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...

el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...

免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...

恶补电源:1.电桥
一、元器件的选择 搜索并选择电桥,再multisim中选择FWB,就有各种型号的电桥: 电桥是用来干嘛的呢? 它是一个由四个二极管搭成的“桥梁”形状的电路,用来把交流电(AC)变成直流电(DC)。…...
6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙
Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...