算法训练营第四十一天 | LeetCode 509 斐波那契数列、LeetCode 70 爬楼梯、LeetCode 746 使用最小花费爬楼梯
LeetCode 509 斐波那契数列
这题动规五部曲都定义得比较明确。首先是dp数组下标,题目中给定F(0) = 0说明从0开始,dp[i]直接表示F(i)的值即可。递推公式也直接给出了,也给了开头两个作为递推基础的数值作为初始化依据。遍历顺序也指明是从前往后(即由下标从小到大递推)。
但是举例推导这一步也是不能省的,比如如果n小于等于1,那么就不能对dp[1]按照题目条件直接初始化,会报错。
最后代码如下:
class Solution {public int fib(int n) {if (n == 0 || n == 1) return n;int[] num = new int[n + 1];for (int i = 0; i <= n; i++) num[i] = 0;num[0] = 0; num[1] = 1;for (int i = 2; i <= n; i++) {num[i] = num[i - 1] + num[i - 2];}return num[n];}
}
LeetCode 70 爬楼梯
这题最后代码写出来很短,但其实用动规来写不是很简单。
首先我们要明确为什么要用动规。这题其实可以用回溯,也可以用递归。但是回溯更适合记录路径,递归需要消耗内存较大。而动规很好地拟合了这道题目,同时时间和空间开销都没有前两种方法那么高。
动规本意也就在这里——用循环和递推条件直接解决问题。但是代价就是想的东西要多一些,也就是我们要找出子问题到当前问题的推导条件和它们之间的关系,比如这题就是两级台阶下的位置到当前位置可以一步到,一级台阶下的位置到当前位置可以一步到,我们将这两个子问题的方法数加起来就得到了当前问题的解。但是问题来了,为什么不让两级前的台阶走两步呢?但按照我们对dp数组和下标的定义,dp[i]是走到第i级台阶的方法数,上面这个问题实际上属于一级前台阶方法数而不属于两级前台阶方法数了。而且用这种视角来思考的话,用的就不是动规,因为那不是子问题到当前问题的推导,而是实际事情发生中的状态。这是动规和平常思路之间最大的差别了。
到这里我们递推公式和dp数组定义和下标含义就都得出来了。接下来初始化方法和遍历顺序是这样:我们找出能够和最开始子问题发生关联的最大下标,把它在递推公式中的子问题dp值初始化即可。这里我们需要结合实际情况设置dp[0]和dp[1]为1,因为能够和最开始一级台阶都没爬的时候的子问题发生关联的最大下标就是2了。遍历顺序从小到大也就是从前往后进行。
举例推导方面和上一题差不多,主要就是对比较小的时候的一些特例进行特殊考量。
代码如下:
class Solution {public int climbStairs(int n) {if (n == 1) return 1;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];}
}
LeetCode 746 使用最小花费爬楼梯
这题其实和上一题很像,不过递推逻辑要稍微变一下,变成取两级之前台阶+从该台阶跳上来开销和一级之前台阶+从该台阶跳上来开销中比较小的那个。子问题和当前问题之间关系是一样的。所以dp数组下标和含义基本一致。这题由于加入了开销,所以也无法像上一题那样从所有台阶下面开始往上跳,初始化时候直接将dp[0]和dp[1]初始化为1即可,原因和上一题一样,这里不再赘述。
遍历顺序从下往上对应也是从小到大。
代码如下:
class Solution {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];}
}
很简洁,但背后思考过程很丰富。
相关文章:
算法训练营第四十一天 | LeetCode 509 斐波那契数列、LeetCode 70 爬楼梯、LeetCode 746 使用最小花费爬楼梯
LeetCode 509 斐波那契数列 这题动规五部曲都定义得比较明确。首先是dp数组下标,题目中给定F(0) 0说明从0开始,dp[i]直接表示F(i)的值即可。递推公式也直接给出了,也给了开头两个作为递推基础的数值作为初始化依据。遍历顺序也指明是从前往…...
网络其他重要协议(DNS、ICMP、NAT)
1.DNS DNS是一整套从域名映射到IP的系统 1.1 DNS背景 TCP/IP中使用IP地址和端口号来确定网络上的一台主机的一个程序,但是IP地址不方便记忆,例如我们想访问百度就会在浏览器中输入baidu.com而不是百度的IP地址。于是人们发明了一种叫主机名的东西, 是…...
利用PyCSP3库(含大量全局约束)进行组合约束建模
文章目录 1. 什么是 PyCSP3 ?2. 安装方法(Windows)2.1 通过 Google_colab 直接运行2.2 通过 pip 进行安装3. 快速入门3.1 声明变量3.2 更新约束3.3 定义目标3.4 常用的全局约束1. 什么是 PyCSP3 ? PyCSP3 是 Python 中的一个库,用于对组合约束问题进行建模,包括 约束满足…...
解决updateByExample时属性值异常的问题(部分属性值没有使用占位符?进行占位,而是变成了属性的名称)
目录 场景简介代码片断实体类 报错信息排查原因解决测试过程解决方案 场景简介 1、程序将mybatis框架升级为3.5.9版本后执行updateByExample方法时报错 代码片断 Condition condition new Condition(MbCcsSessionConfig.class); condition.createCriteria().andEqualTo(&quo…...
[C++][algorithm][Eigen] 基于Eigen实现Softmax函数
1 简介 Softmax函数是机器学习和深度学习中一个非常重要的激活函数,它在多分类问题中尤其关键。Softmax函数能够将一个向量或一组实数转换成概率分布,使得每个元素的值都在0到1之间,并且所有元素的和为1。本博客文章《【Eigen】基于Eigen实现…...
一招教大家,如何移除受保护的excel工作表的编辑权限限制?
有时候,我们打开工作表发现只有部分单元格可以编辑,点击其他单元格都显示“您试图更改的单元格或图标受保护”,既没法正常编辑或下拉填充,也没有办法快捷筛选。这时候我们可以通过输入密码解除保护,就可以正常编辑了。…...
Python 全栈体系【四阶】(五十三)
第五章 深度学习 十二、光学字符识别(OCR) 2. 文字检测技术 2.3 DB(2020) DB全称是Differentiable Binarization(可微分二值化),是近年提出的利用图像分割方法进行文字检测的模型。前文所提…...
民国漫画杂志《时代漫画》第27期.PDF
时代漫画27.PDF: https://url03.ctfile.com/f/1779803-1248635258-b6a842?p9586 (访问密码: 9586) 《时代漫画》的杂志在1934年诞生了,截止1937年6月战争来临被迫停刊共发行了39期。 ps: 资源来源网络!...
图论(四)—最短路问题(Dijkstra)
一、最短路 概念:从某个点 A 到另一个点B的最短距离(或路径)。从点 A 到 B 可能有多条路线,多种距离,求其中最短的距离和相应路径。 最短路径分类: 单源最短路:图中的一个点到其余各点的最短路径…...
用友NC linkVoucher SQL注入漏洞复现
0x01 产品简介 用友NC是由用友公司开发的一套面向大型企业和集团型企业的管理软件产品系列。这一系列产品基于全球最新的互联网技术、云计算技术和移动应用技术,旨在帮助企业创新管理模式、引领商业变革。 0x02 漏洞概述 用友NC /portal/pt/yercommon/linkVoucher 接口存在…...
部署Prometheus + Grafana实现监控数据指标
1.1 Prometheus安装部署 Prometheus监控服务 主机名IP地址系统配置作用Prometheus192.168.110.27/24CentOS 7.94颗CPU 8G内存 100G硬盘Prometheus服务器grafana192.168.110.28/24CentOS 7.94颗CPU 8G内存 100G硬盘grafana服务器 监控机器 主机名IP地址系统配置k8s-master-0…...
GEE27:遥感数据可用数据源计算及条带号制作
1.写在前面 🌍✨今天读了一篇关于遥感数据可用数据源计算及条带号制作的文章,结合着自己的理解,添加了一些内容。 2.GEE代码 📚📚这段代码的主要作用是利用Google Earth Engine平台,通过分析Landsat 8影…...
FURNet问题
1. 为什么选择使用弱监督学习? 弱监督学习减少了对精确标注数据的依赖,这在医学图像处理中尤为重要,因为高质量标注数据通常需要大量专业知识和时间。弱监督学习通过利用少量标注数据或粗略标注数据来训练模型,降低了数据准备的成…...
抖音小店怎么对接达人合作?达人带货的细节分享,附邀约达人话术
大家好,我是电商花花 人有多大胆,地就有多大产,做抖店想要出单,爆单,那必须要对接大量的达人来帮我们带货,抖音小店就是直播电商,帮我们对接的达人越多,出单就越多。 所以做抖店如…...
迈向未来:Web3 技术开发的无限可能
在当今的数字时代,互联网技术日新月异,推动着各行各业的变革与发展。从Web1.0的信息发布,到Web2.0的社交互动,互联网的每一次进化都为人们的生活带来了深远的影响。如今,Web3的到来正在开启一个全新的时代,…...
Python应用开发——30天学习Streamlit Python包进行APP的构建(2)
🗓️ 天 14 Streamlit 组件s Streamlit 组件s 是第三方的 Python 模块,对 Streamlit 进行拓展 [1]. 有哪些可用的 Streamlit 组件s? 好几十个精选 Streamlit 组件s 罗列在 Streamlit 的网站上 [2]. Fanilo(一位 Streamlit 创作者)在 wiki 帖子中组织了一个很棒的 St…...
Leecode热题100---46:全排列(递归)
题目: 给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 思路: 元素交换函数递归: 通过交换元素来实现全排列。即对于[x, nums.size()]中的元素,for循环遍历每个元素分别成…...
Android 多语言
0. Locale方法 Locale locale Locale.forLanguageTag("zh-Hans-CN"); 执行如下方法返回字符串如下: 方法 英文下执行 中文下执行 备注 getLanguage()zhzhgetCountry()CNCNgetDisplayLanguage()zh中文getDisplayCountry()CN中国getDisplayName()zh (…...
Thingsboard规则链:Message Type Filter节点详解
一、Message Type Filter节点概述 二、具体作用 三、使用教程 四、源码浅析 五、应用场景与案例 智能家居自动化 工业设备监控 智慧城市基础设施管理 六、结语 在物联网(IoT)领域,数据处理与自动化流程的实现是构建智能系统的关键。作…...
SQLI-labs-第二十五关和第二十五a关
目录 第二十五关 1、判断注入点 2、判断数据库 3、判断表名 4、判断字段名 5、获取数据库的数据 第二十五a关 1、判断注入点 2、判断数据库 第二十五关 知识点:绕过and、or过滤 思路: 通过分析源码和页面,我们可以知道对and和or 进…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...
TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?
在工业自动化持续演进的今天,通信网络的角色正变得愈发关键。 2025年6月6日,为期三天的华南国际工业博览会在深圳国际会展中心(宝安)圆满落幕。作为国内工业通信领域的技术型企业,光路科技(Fiberroad&…...
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...
