代码随想录算法训练营第三十二天|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) 是一种结构型设计模式,它允许将对象组合成树形结构来表示“部分-整体”的层次结构。组合模式使得客户端对单个对象和组合对象的使用具有一致性。换句话说,组合模式允…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...

Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理
在城市的某个角落,一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延,滚滚浓烟弥漫开来,周围群众的生命财产安全受到严重威胁。就在这千钧一发之际,消防救援队伍迅速行动,而豪越科技消防一体化安全管控平台构建的消防“…...

spring Security对RBAC及其ABAC的支持使用
RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型,它将权限分配给角色,再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...
【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统
Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...

倒装芯片凸点成型工艺
UBM(Under Bump Metallization)与Bump(焊球)形成工艺流程。我们可以将整张流程图分为三大阶段来理解: 🔧 一、UBM(Under Bump Metallization)工艺流程(黄色区域ÿ…...