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

算法训练营第四十一天 | 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数组下标&#xff0c;题目中给定F(0) 0说明从0开始&#xff0c;dp[i]直接表示F(i)的值即可。递推公式也直接给出了&#xff0c;也给了开头两个作为递推基础的数值作为初始化依据。遍历顺序也指明是从前往…...

网络其他重要协议(DNS、ICMP、NAT)

1.DNS DNS是一整套从域名映射到IP的系统 1.1 DNS背景 TCP/IP中使用IP地址和端口号来确定网络上的一台主机的一个程序&#xff0c;但是IP地址不方便记忆&#xff0c;例如我们想访问百度就会在浏览器中输入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函数是机器学习和深度学习中一个非常重要的激活函数&#xff0c;它在多分类问题中尤其关键。Softmax函数能够将一个向量或一组实数转换成概率分布&#xff0c;使得每个元素的值都在0到1之间&#xff0c;并且所有元素的和为1。本博客文章《【Eigen】基于Eigen实现…...

一招教大家,如何移除受保护的excel工作表的编辑权限限制?

有时候&#xff0c;我们打开工作表发现只有部分单元格可以编辑&#xff0c;点击其他单元格都显示“您试图更改的单元格或图标受保护”&#xff0c;既没法正常编辑或下拉填充&#xff0c;也没有办法快捷筛选。这时候我们可以通过输入密码解除保护&#xff0c;就可以正常编辑了。…...

Python 全栈体系【四阶】(五十三)

第五章 深度学习 十二、光学字符识别&#xff08;OCR&#xff09; 2. 文字检测技术 2.3 DB&#xff08;2020&#xff09; DB全称是Differentiable Binarization&#xff08;可微分二值化&#xff09;&#xff0c;是近年提出的利用图像分割方法进行文字检测的模型。前文所提…...

民国漫画杂志《时代漫画》第27期.PDF

时代漫画27.PDF: https://url03.ctfile.com/f/1779803-1248635258-b6a842?p9586 (访问密码: 9586) 《时代漫画》的杂志在1934年诞生了&#xff0c;截止1937年6月战争来临被迫停刊共发行了39期。 ps: 资源来源网络!...

图论(四)—最短路问题(Dijkstra)

一、最短路 概念&#xff1a;从某个点 A 到另一个点B的最短距离&#xff08;或路径&#xff09;。从点 A 到 B 可能有多条路线&#xff0c;多种距离&#xff0c;求其中最短的距离和相应路径。 最短路径分类&#xff1a; 单源最短路&#xff1a;图中的一个点到其余各点的最短路径…...

用友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.写在前面 &#x1f30d;✨今天读了一篇关于遥感数据可用数据源计算及条带号制作的文章&#xff0c;结合着自己的理解&#xff0c;添加了一些内容。 2.GEE代码 &#x1f4da;&#x1f4da;这段代码的主要作用是利用Google Earth Engine平台&#xff0c;通过分析Landsat 8影…...

FURNet问题

1. 为什么选择使用弱监督学习&#xff1f; 弱监督学习减少了对精确标注数据的依赖&#xff0c;这在医学图像处理中尤为重要&#xff0c;因为高质量标注数据通常需要大量专业知识和时间。弱监督学习通过利用少量标注数据或粗略标注数据来训练模型&#xff0c;降低了数据准备的成…...

抖音小店怎么对接达人合作?达人带货的细节分享,附邀约达人话术

大家好&#xff0c;我是电商花花 人有多大胆&#xff0c;地就有多大产&#xff0c;做抖店想要出单&#xff0c;爆单&#xff0c;那必须要对接大量的达人来帮我们带货&#xff0c;抖音小店就是直播电商&#xff0c;帮我们对接的达人越多&#xff0c;出单就越多。 所以做抖店如…...

迈向未来:Web3 技术开发的无限可能

在当今的数字时代&#xff0c;互联网技术日新月异&#xff0c;推动着各行各业的变革与发展。从Web1.0的信息发布&#xff0c;到Web2.0的社交互动&#xff0c;互联网的每一次进化都为人们的生活带来了深远的影响。如今&#xff0c;Web3的到来正在开启一个全新的时代&#xff0c;…...

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:全排列(递归)

题目&#xff1a; 给定一个不含重复数字的数组 nums &#xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 思路&#xff1a; 元素交换函数递归&#xff1a; 通过交换元素来实现全排列。即对于[x, nums.size()]中的元素&#xff0c;for循环遍历每个元素分别成…...

Android 多语言

0. Locale方法 Locale locale Locale.forLanguageTag("zh-Hans-CN"); 执行如下方法返回字符串如下&#xff1a; 方法 英文下执行 中文下执行 备注 getLanguage()zhzhgetCountry()CNCNgetDisplayLanguage()zh中文getDisplayCountry()CN中国getDisplayName()zh (…...

Thingsboard规则链:Message Type Filter节点详解

一、Message Type Filter节点概述 二、具体作用 三、使用教程 四、源码浅析 五、应用场景与案例 智能家居自动化 工业设备监控 智慧城市基础设施管理 六、结语 在物联网&#xff08;IoT&#xff09;领域&#xff0c;数据处理与自动化流程的实现是构建智能系统的关键。作…...

SQLI-labs-第二十五关和第二十五a关

目录 第二十五关 1、判断注入点 2、判断数据库 3、判断表名 4、判断字段名 5、获取数据库的数据 第二十五a关 1、判断注入点 2、判断数据库 第二十五关 知识点&#xff1a;绕过and、or过滤 思路&#xff1a; 通过分析源码和页面&#xff0c;我们可以知道对and和or 进…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...

0x-3-Oracle 23 ai-sqlcl 25.1 集成安装-配置和优化

是不是受够了安装了oracle database之后sqlplus的简陋&#xff0c;无法删除无法上下翻页的苦恼。 可以安装readline和rlwrap插件的话&#xff0c;配置.bahs_profile后也能解决上下翻页这些&#xff0c;但是很多生产环境无法安装rpm包。 oracle提供了sqlcl免费许可&#xff0c…...