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是同步通信,有两个线一个是时钟信号线,一个数数据…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...

Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...