代码随想录算法训练营第三十二天|509.斐波那契数、70.爬楼梯、746.使用最小花费爬楼梯
目录
509.斐波那契数
动态规划五部曲:
1.确定dp数组(dp table)以及下标的含义
2.确定递推公式
3.dp数组如何初始化
4.确定遍历顺序
5.举例推导dp数组
70.爬楼梯
动态规划五部曲:
1.确定dp数组(dp table)以及下标的含义
2.确定递推公式
3.dp数组如何初始化
4.确定遍历顺序
5.举例推导dp数组
746.使用最小花费爬楼梯
动态规划五部曲:
1.确定dp数组(dp table)以及下标的含义
2.确定递推公式
3.dp数组如何初始化
4.确定遍历顺序
5.举例推导dp数组
509.斐波那契数
题目链接:509. 斐波那契数 - 力扣(LeetCode)
动态规划五部曲:
1.确定dp数组(dp table)以及下标的含义
dp[i]表示第i项斐波那契数列
2.确定递推公式
第i项斐波那契数列 = 前两项之和,即dp[i] = dp[i-1] + dp[i-2];
3.dp数组如何初始化
递推公式的i = 0和i = 1不符合递推公式,且是最边界情况,特别处理,
即dp[0] = 0,dp[1] = 1;
4.确定遍历顺序
从第三个数据位置开始遍历
5.举例推导dp数组
dp[2]、dp[3]符合,递推到dp[...]都可行
class Solution
{
public:int fib(int n) {vector<int> dp(n+10);dp[0] = 0;dp[1] = 1;for(int i=2; i<=n; i++){dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
};
70.爬楼梯
题目链接:70. 爬楼梯 - 力扣(LeetCode)
动态规划五部曲:
1.确定dp数组(dp table)以及下标的含义
dp[i]表示第i个台阶的方案数
2.确定递推公式
1阶:1
2阶:2
3阶:先走一步,如果一步走一阶,剩2阶,方案数为2,
如果一步走两阶,剩1阶方案数为1,方案数总共2+1 = 3
4阶:先走一步,如果一步走一阶,剩3阶,方案数为3,
如果一步走两阶,剩2阶方案数为2,方案数总共3+2 = 5
5阶:先走一步,如果一步走一阶,剩4阶,方案数为5,
如果一步走两阶,剩3阶方案数为3,方案数总共5+3 = 8
总结:当前台阶i的方案数 = i-1台阶方案数 +i-2台阶方案数
即,dp[i] = dp[i-1] + dp[i-2]
3.dp数组如何初始化
递推公式的i = 1和i = 2不符合递推公式,且是最边界情况,特别处理,
即dp[1] = 1,dp[2] = 2;
4.确定遍历顺序
从第三个数据位置开始遍历
5.举例推导dp数组
第二步推到过了可行。
class Solution {
public:int climbStairs(int n) {vector<int> dp(n+10);dp[1] = 1;dp[2] = 2;for(int i=3; i<=n; i++){dp[i] = dp[i-1] + dp[i-2]; // i-1台阶的方案数 +i-2台阶的方案数 } return dp[n];}
};
746.使用最小花费爬楼梯
题目链接:746. 使用最小花费爬楼梯 - 力扣(LeetCode)
动态规划五部曲:
1.确定dp数组(dp table)以及下标的含义
dp[i]表示到达第i个台阶所花的最小费用
2.确定递推公式
0阶:0元。
1阶:0元。
2阶:min(到达(2-1)阶的费用+(2-1)阶跳的费用 , 到达(2-2)阶的费用 +(2-2)阶跳的费用)。
3阶:min(到达(3-1)阶的费用+(3-1)阶跳的费用 , 到达(3-2)阶的费用 +(3-2)阶跳的费用)。
4阶:min(到达(4-1)阶的费用+(4-1)阶跳的费用 , 到达(4-2)阶的费用 +(4-2)阶跳的费用)。
整体看感觉思路可行:即,dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])。
3.dp数组如何初始化
第0阶和第1阶的为起点,不需要花费价钱,故dp[0] = 0, dp[1] = 0。
4.确定遍历顺序
从第三个数据位置开始遍历
5.举例推导dp数组
按预期,数据是从第0个台阶依次到第n个台阶(顶点)的变化,所以数据是递推过去的,担心min()可能取0的值,验证了i = 2的程序,和i = 3的清楚,数据按预测的递推过程进行变化,可行。
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size()+10);dp[0] = 0;dp[1] = 0;int n = cost.size();for(int i=2; i<=n; i++){// i-1往上爬 或者i-2往上爬,取最小dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]); // 通过这个输出+题目信息把"<n"改成了"<=n",了解到n-1是台阶,而不是到顶// cout<<dp[i]<<' '<<dp[i-1]+cost[i-1]<<' '<<dp[i-2]+cost[i-2]<<'\n'; }return dp[n];}
};
相关文章:
代码随想录算法训练营第三十二天|509.斐波那契数、70.爬楼梯、746.使用最小花费爬楼梯
目录 509.斐波那契数 动态规划五部曲: 1.确定dp数组(dp table)以及下标的含义 2.确定递推公式 3.dp数组如何初始化 4.确定遍历顺序 5.举例推导dp数组 70.爬楼梯 动态规划五部曲: 1.确定dp数组(dp table)…...
【2024年华为OD机试】 (A卷,100分)- 总最快检测效率(Java JS PythonC/C++)
一、问题描述 题目描述 在系统、网络均正常的情况下组织核酸采样员和志愿者对人群进行核酸检测筛查。 每名采样员的效率不同,采样效率为 N 人/小时。由于外界变化,采样员的效率会以 M 人/小时为粒度发生变化,M 为采样效率浮动粒度…...
【大数据】Apache Superset:可视化开源架构
Apache Superset是什么 Apache Superset 是一个开源的现代化数据可视化和数据探索平台,主要用于帮助用户以交互式的方式分析和展示数据。有不少丰富的可视化组件,可以将数据从多种数据源(如 SQL 数据库、数据仓库、NoSQL 数据库等࿰…...
LabVIEW调用不定长数组 DLL数组
在使用 LabVIEW 调用 DLL 库函数时,如果函数中的结构体包含不定长数组,直接通过 调用库函数节点(Call Library Function Node) 调用通常会遇到问题。这是因为 LabVIEW 需要与 DLL 中的数据结构完全匹配,而包含不定长数…...
MySQL 17 章——触发器
在实际开发中,我们经常会遇到这样的情况:有2个或者多个相关联的表,比如商品信息表和库存信息表,分别存放在两个不同的数据表中,我们在添加一条新商品记录的时候,为了保证数据的完整性,必须同时在…...
面向对象分析与设计Python版 面向对象设计方法
文章目录 前言一、职责驱动设计二、职责驱动设计-案例 前言 面向对象设计目标:在面向对象分析建立的领域模型的基础上,定义对象操作(职责)。为对象分配职责的方法有: 职责驱动设计遵循GRASP设计原则(Gene…...
GB/T 19582.1-2008主要内容
标准背景与概述 GB/T 19582.1-2008是由中国国家标准化管理委员会发布的国家标准,旨在指导和规范基于Modbus协议的工业自动化网络的设计和实施。该标准由全国工业过程测量控制和自动化标准化技术委员会(TC124)归口,并由中国机械工…...
[石榴翻译] 维吾尔语音识别 + TTS语音合成
API网址 丝路AI平台 获取 Access token 接口地址:https://open.xjguoyu.cn/api/auth/oauth/token,请求方式:GET,POST Access token是调用服务API的凭证,调用服务API之前需要获取 token。每次成功获取 token 以后只有…...
算法题(32):三数之和
审题: 需要我们找到满足以下三个条件的所有三元组,并存在二维数组中返回 1.三个元素相加为0 2.三个元素的下标不可相同 3.三元组的元素不可相同 思路: 混乱的数据不利于进行操作,所以我们先进行排序 我们可以采取枚举的方法进行解…...
webpack03
什么是source-map 将代码编译压缩之后,,可以通过source-map映射会原来的代码,,,在调试的时候可以准确找到原代码报错位置,,,进行修改 source-map有很多值: eval &#…...
组会 | SNN 的 BPTT(backpropagation through time)
目录 1 神经学基础知识1.1 神经元1.2 神经元之间的连接1.3 膜电位1.4 去极化与超极化 2 SNN2.1 LIF 模型2.2 BPTT 中存在的问题2.3 梯度爆炸或消失问题 前言: 本博仅为组会总结,如有谬误,请不吝指正!虽然标题为 BPTT&am…...
CDA数据分析师一级经典错题知识点总结(3)
1、SEMMA 的基本思想是从样本数据开始,通过统计分析与可视化技术,发现并转换最有价值的预测变量,根据变量进行构建模型,并检验模型的可用性和准确性。【强调探索性】 2、CRISP-DM模型Cross Industry Standard Process of Data Mi…...
django基于Python的电影推荐系统
Django 基于 Python 的电影推荐系统 一、系统概述 Django 基于 Python 的电影推荐系统是一款利用 Django 框架开发的智能化应用程序,旨在为电影爱好者提供个性化的电影推荐服务。该系统通过收集和分析用户的观影历史、评分数据、电影的属性信息(如类型…...
JVM与Java体系结构
一、前言: Java语言和JVM简介: Java是目前最为广泛的软件开发平台之一。 JVM:跨语言的平台 随着Java7的正式发布,Java虚拟机的设计者们通过JSR-292规范基本实现在Java虚拟机平台上运行非Java语言编写的程序。 Java虚拟机根本不关心运行在其内部的程序到底是使用何…...
网络授时笔记
SNTP的全称是Simple Network Time Protocol,意思是简单网络时间协议,用来从网络中获取当前的时间,也可以称为网络授时。项目中会使用LwIP SNTP模块从服务器(pool.ntp.org)获取时间 我们使用sntp例程,sntp例程路径为D:\Espressif\…...
【CSS】HTML页面定位CSS - position 属性 relative 、absolute、fixed 、sticky
目录 relative 相对定位 absolute 绝对定位 fixed 固定定位 sticky 粘性定位 position:relative 、absolute、fixed 、sticky (四选一) top:距离上面的像素 bottom:距离底部的像素 left:距离左边的像素…...
spark汇总
目录 描述运行模式1. Windows模式代码示例 2. Local模式3. Standalone模式 RDD描述特性RDD创建代码示例(并行化创建)代码示例(读取外部数据)代码示例(读取目录下的所有文件) 算子DAGSparkSQLSparkStreaming…...
【Rust自学】11.5. 在测试中使用Result<T, E>
喜欢的话别忘了点赞、收藏加关注哦,对接下来的教程有兴趣的可以关注专栏。谢谢喵!(・ω・) 11.5.1. 测试函数返回值为Result枚举 到目前为止,测试运行失败的原因都是因为触发了panic,但可以导致测试失败的…...
Sping Boot教程之五十四:Spring Boot Kafka 生产者示例
Spring Boot Kafka 生产者示例 Spring Boot 是 Java 编程语言中最流行和使用最多的框架之一。它是一个基于微服务的框架,使用 Spring Boot 制作生产就绪的应用程序只需很少的时间。Spring Boot 可以轻松创建独立的、生产级的基于 Spring 的应用程序,您可…...
设计模式-结构型-组合模式
1. 什么是组合模式? 组合模式(Composite Pattern) 是一种结构型设计模式,它允许将对象组合成树形结构来表示“部分-整体”的层次结构。组合模式使得客户端对单个对象和组合对象的使用具有一致性。换句话说,组合模式允…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...
