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

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. 斐波那契数 斐波那契数 题目 斐波那契数 &#xff08;通常用 F(n) 表示&#xff09;形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始&#xff0c;后面的每一项数字都是前面两项数字的和。也就是&#xff1a; F(0) 0&#xff0c;F(1) 1 F(n) F(n -…...

【开源移植】MultiButton_小型按键驱动模块移植

MultiButton 简介 MultiButton 是一个小巧简单易用的事件驱动型按键驱动模块&#xff0c;可无限量扩展按键&#xff0c;按键事件的回调异步处理方式可以简化你的程序结构&#xff0c;去除冗余的按键处理硬编码&#xff0c;让你的按键业务逻辑更清晰。 使用方法 1.先申请一个…...

【Python系列】Python 字典合并

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

C# 设计模式之装饰器模式

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

【uniapp离线打包】(基于Android studio)

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

稳稳的年化10%,多任务时序动量策略——基于pytorch的深度学习策略(附python代码)

原创文章第608篇&#xff0c;专注“AI量化投资、世界运行的规律、个人成长与财富自由"。 做因子挖掘这段时间&#xff0c;有一个观感。 传统的因子挖掘&#xff0c;尤其是手工构造因子&#xff0c;到遗传算法因子挖掘。——本身也是一种”拟合“&#xff0c;或者说试图”…...

C++分析AVL树

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

aurora8b10b ip的使用(framing接口下的数据回环测试)

文章目录 一、Aurora8B/10B协议二、时钟、复位与状态指示1、时钟2、复位3、状态指示 三、数据发送、接受接口&#xff08;1&#xff09;AXI4-Stream位排序&#xff08;2&#xff09;Streaming接口&#xff08;3&#xff09;Framing接口&#xff08;帧传输接口&#xff09; 四、…...

如何通过OpenCV判断图片是否包含在视频内?

要判断图片是否包含在视频内&#xff0c;可以使用计算机视觉技术和图像处理方法。这通常涉及特征匹配或模板匹配。以下是一个基于OpenCV的解决方案&#xff0c;通过特征匹配的方法来实现这一目标。 步骤概述 读取视频和图片&#xff1a; 使用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的时候&#xff0c;在执行Action时依然还是通过text-based&#xff08;文本模态&#xff09;后者JSO…...

循环结构(三)——do-while语句

目录 &#x1f341;引言 &#x1f341;一、语句格式 &#x1f680;格式1 &#x1f680;格式2 &#x1f341;二、语句执行过程 &#x1f341;三、实例 &#x1f680;【例1】 &#x1f680;【例2】 &#x1f680;【例3】 &#x1f341;总结 &#x1f341;备注 &am…...

pandas 或筛选

pandas 或筛选 在Pandas中&#xff0c;可以使用DataFrame.loc方法结合逻辑运算符来实现或筛选。这里提供一个简单的例子&#xff1a; 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

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

【从零开始一步步学习VSOA开发】快速体验SylixOS

快速体验SylixOS 安装完毕RealEvo-IDE 后&#xff0c;同时也安装了RealEvo-Simulator。RealEvo-Simulator 是一个虚拟运行环境&#xff0c;可以模拟各种体系结构并在其上运行 SylixOS。相比于物理板卡&#xff0c;在 RealEvo-Simulator 进行运行调测更加的方便快捷且成本低廉。…...

Ansible自动化:简化IT基础设施管理的艺术

目录 一.前言 二.Ansible简介 2.1什么是Ansible&#xff1f; 2.2Ansible的主要特点 2.3Ansible的应用场景 三.探索Ansible的高级功能 3.1 高级Playbook特性 3.2 Ansible Vault 3.3 动态Inventory 3.4Ansible Tower&#xff08;AWX&#xff09; 3.5模块开发 3.6 Ans…...

【Rust光年纪】探索Rust语言中的WebSocket库和框架:优劣一览

Rust语言中的实时通信利器&#xff1a;WebSocket库与框架全面解析 前言 随着Rust语言的不断发展&#xff0c;其在Web开发领域也变得越来越受欢迎。WebSocket作为实现实时通信的重要技术&#xff0c;在Rust的生态系统中也有多个库和框架提供了支持。本文将介绍几个主流的Rust …...

HTML 基础结构

目录 1. 文档声明 2. 根标签 3. 头部元素 4. 主题元素 5. 注释 6. 演示 1. 文档声明 <!DOCTYPE html>&#xff1a;声明文档类型&#xff0c;表示该文档是 html 文档&#xff0c; 2. 根标签 &#xff08;1&#xff09;所有的其他标签都要放在一对根标签中&#…...

多页合同怎么盖骑缝章_电子合同怎么盖骑缝章?

多页合同怎么盖骑缝章&#xff1f;电子合同怎么盖骑缝章&#xff1f; 对于纸质多页合同&#xff0c;盖骑缝章是一种常见的做法&#xff0c;用于确保合同的完整性&#xff0c;防止任何页面被替换或篡改。以下是盖骑缝章的基本步骤&#xff1a; 将所有合同页面平铺在桌面上。用…...

GD 32 IIC通信协议

前言&#xff1a; ... 通信方式 通信方式分为串行通信和并行通信。常见的串口就是串行通信的方式 常用的串行通信接口 常用的串行通信方式有USART,IIC,USB,CAN总线 同步与异步 同步通信&#xff1a;IIC是同步通信&#xff0c;有两个线一个是时钟信号线&#xff0c;一个数数据…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...

ubuntu22.04 安装docker 和docker-compose

首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...