代码随想录算法训练营第51期第32天 | 理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯
理论基础
动态规划:dp,每一个状态都是由上个状态推导出来的,因为我是先写完三道题再看理论的,所以有点感概;
- 确定dp数组(dp table)以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
509. 斐波那契数
509. 斐波那契数
https://leetcode.cn/problems/fibonacci-number/
1.因为是n是动态的,所以需要用malloc来分配内存,因为后面会对dp赋值,所以初始化的代码我注释了
2.因为求n,但下标0是从开始的,所以需要n+1
3.这里也可以用递归写,但是复杂度有点2的n次方,我就不记录了
4.我还记录了只需要用2个变量来存储结果的写法,这样就不需要用数组了
动归五部曲
1.确定dp数组以及下标的含义:dp[i]表示第i个斐波那契数
2.确定递推公式:dp[i] = dp[i-1] + dp[i-2]
3.dp数组如何初始化:dp[0] = 0, dp[1] = 1
4.确定遍历顺序:从前往后遍历
5.举例推导 a = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] ,这里n=10,但是a[10]是第11个斐波那契数,所以需要n+1
int fib(int n) {if (n <= 1) {return n;}n = n + 1;int *dp = (int*)malloc(sizeof(int) * n);// for (int i = 0; i < n; i++) {// dp[i] = 0;// }dp[0] = 0;dp[1] = 1;for (int i = 2; i < n; i++) {dp[i] = dp[i-1] + dp[i-2];}return dp[n-1];
}//这里也可以用递归写,但是复杂度有点2的n次方,我就不记录了
int fib(int n) {if (n <= 1) {return n;}int fir = 0;int sec = 1;int tmp = 0;for (int i = 2; i <= n ; i++) {tmp = fir + sec;fir = sec;sec = tmp;}return sec;
}
70. 爬楼梯
70. 爬楼梯
https://leetcode.cn/problems/climbing-stairs/MD,写在vscode上的东西丢了,我还得再写一次
1.这里和上一题一样,代码也差不多,除了初始化,其他代码都可以复用了。
动归五部曲
1.确定dp数组以及下标的含义:dp[i]表示第i个斐波那契数
2.确定递推公式:dp[i] = dp[i-1] + dp[i-2]
3.dp数组如何初始化:dp[1] = 1, dp[2] = 2, 这里dp[0]没有意义,但是为了统一,我还是初始化为0
4.确定遍历顺序:从前往后遍历
5.举例推导如下:
1:1
2:1, 2
3:1+1+1,2+1,1+2
4:1+1+1+1,2+1+1,1+2+1,1+1+2,2+2
这里4是第3层再加1和第2层再加2,所以4是第3层和第2层的和,所以dp[4] = dp[3] + dp[2]
int climbStairs(int n) {if (n <= 3) {return n;}n = n + 1;int *dp = (int *)malloc(sizeof(int) * n);dp[0] = 0;dp[1] = 1;dp[2] = 2;for (int i = 3; i < n; i++) {dp[i] = dp[i-2] + dp[i-1];}return dp[n-1];
}int climbStairs(int n) {if (n <= 2) {return n;}int pre = 1;int cur = 2;int tmp = 0;for (int i = 3; i <= n; i++) {tmp = pre + cur;pre = cur;cur = tmp;}return cur;
}
746. 使用最小花费爬楼梯
746. 使用最小花费爬楼梯
https://leetcode.cn/problems/min-cost-climbing-stairs/1.这一题虽然说简单,但是还真不太容易想到
动归五部曲
1.确定dp数组以及下标的含义:dp[i]表示踏上该楼梯的最小花费(不包括当前楼梯的花费)
2.确定递推公式:dp[i] = min((dp[i-1] + cost[i]), (dp[i-2] + cost[i]));
3.dp数组如何初始化:dp[0] = cost[0], dp[1] = cost[1],这里就不是简单的直接加了,而且后续因为长度只有costSize,和题目要求的顶部还差一点,所以需要再求一次
4.确定遍历顺序:从前往后遍历
5.举例推导:无
#define min(a, b) (((a) < (b)) ? (a) :(b))
int minCostClimbingStairs(int* cost, int costSize) {int *dp = (int *)malloc(sizeof(int) * costSize);dp[0] = cost[0];dp[1] = cost[1];for (int i = 2; i < costSize; i++) {dp[i] = min((dp[i-1] + cost[i]), (dp[i-2] + cost[i]));}int res = min(dp[costSize-2], dp[costSize-1]);return res;
}
相关文章:
代码随想录算法训练营第51期第32天 | 理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯
理论基础 动态规划:dp,每一个状态都是由上个状态推导出来的,因为我是先写完三道题再看理论的,所以有点感概; 确定dp数组(dp table)以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举…...
爱思唯尔word模板
爱思唯尔word模板 有时候并不一定非得latex https://download.csdn.net/download/qq_38998213/90199214 参考文献书签链接...
每日一题 354. 俄罗斯套娃信封问题
354. 俄罗斯套娃信封问题 需要对信封排序 ,重点是再宽度相同时,逐步减少其高度 class Solution { public:int maxEnvelopes(vector<vector<int>>& envelopes) {sort(envelopes.begin(),envelopes.end(),[](const vector<int>&a,const v…...
ASP.net网站的注册、登录和密码修改的操作详解
一、进入注册、登录和密码修改操作详解 ASP.net网站为用户提供不同权限状态下的操作界面。根据用户登录状态,页面会显示不同的选项。 已登录用户的操作 图1 登录后操作界面 当用户已登录系统时,会显示以下内容和功能: 1. 欢迎信息 页面顶部…...
2024.12.29(进程线程实现并发服务器)
作业 多进程多线程并发服务器实现一遍提交。 服务器 #include <myhead.h> #define PORT 12345 #define IP "192.168.124.123"void *fun(void *fd) {int newfd *(int *)fd;char buff[1024];while(1){int res recv(newfd,buff,sizeof(buff),0);if(res 0){p…...
如何在 Ubuntu 上安装 PyTorch
简介 PyTorch 因其易用性、动态计算图和高效性而日益流行,成为实现深度学习模型的首选。如果你想探索这个工具并学习如何在 Ubuntu 上安装 PyTorch,本指南将对你有所帮助! 在本教程中,我们将引导你完成在 Ubuntu 系统上使用 Pip…...
8-Gin 中间件 --[Gin 框架入门精讲与实战案例] 【文末有测试代码】
路由中间件 Gin 是一个用 Go (Golang) 编写的 HTTP web 框架。它以性能好、中间件支持灵活著称,非常适合用来构建微服务或 RESTful API 服务。下面我将提供三个使用 Gin 的路由中间件的完整示例。 示例 1: 简单的日志记录中间件 这个中间件会在每个请求处理前后打…...
【潜意识Java】深入详细理解分析Java中的toString()方法重写完整笔记总结,超级详细。
目录 一、toString() 方法是啥? (一)默认的 toString() 方法 (二)toString() 方法的作用 二、为啥要重写 toString() 方法? (一)提高代码的可读性 (二)…...
【论文笔记】Contrastive Learning for Sign Language Recognition and Translation
🍎个人主页:小嗷犬的个人主页 🍊个人网站:小嗷犬的技术小站 🥭个人信条:为天地立心,为生民立命,为往圣继绝学,为万世开太平。 基本信息 标题: Contrastive Learning for…...
Gitlab17.7+Jenkins2.4.91实现Fastapi/Django项目持续发布版本详细操作(亲测可用)
一、gitlab设置: 1、进入gitlab选择主页在左侧菜单的下面点击管理员按钮。 2、选择左侧菜单的设置,选择网络,在右侧选择出站请求后选择允许来自webhooks和集成对本地网络的请求 3、webhook设置 进入你自己的项目选择左侧菜单的设置ÿ…...
一起来看--红黑树
【欢迎关注编码小哥,学习更多实用的编程方法和技巧】 红黑树是一种自平衡的二叉搜索树,广泛应用于计算机科学中,尤其是在实现关联数组和集合时。它的设计旨在确保在最坏情况下,基本动态集合操作(如插入、删除和查找&am…...
SpringBoot整合篇 05、Springboot整合Redission
文章目录 前言Redission详细配置步骤pom依赖application.yaml配置类CacheConfigEnvironmentContext RedissionController单测 前言 本篇博客是SpringBoot整合Redission,若文章中出现相关问题,请指出! 所有博客文件目录索引:博客…...
供应链系统设计-供应链中台系统设计(六)- 商品中心概念篇
概述 我们在供应链系统设计-中台系统设计系列(五)- 供应链中台实践概述 中描述了什么是供应链中台,供应链中台主要包含了那些组成部门。包括业务中台、通用中台等概念。为了后续方便大家对于中台有更深入的理解,我会逐一针对中台…...
胡闹厨房练习(三)
ScriptableObject 一、初步了解 1、实质:是一种特殊类型的Unity对象, 2、作用:用于存储大量数据,而不必依附于游戏场景中的某个GameObject。 3、特点: 可以在不增加场景中对象数量的情况下,管理和存储复杂的数据结构、配置信息、游戏状态等。 4、适用:非常适合用来…...
关于ESD(静电放电)等级的划分
关于ESD(静电放电)等级的划分,主要依据不同的测试模型和测试标准。以下是对HBM(人体模型)和CDM(充电器件模型)两种测试模型下ESD等级划分的详细解释: HBM ESD等级划分 HBM ESD等级…...
探究步进电机与输入脉冲的关系
深入了解步进电机 前言一、 步进电机原理二、 细分三、脉冲数总结 前言 主要是探究以下内容: 1、步进电机的步进角。 2、什么是细分。 3、脉冲的计算。 最后再扩展以下STM32定时器的计算方法。 一、 步进电机原理 其实语言描述怎么样都不直观,我更建议…...
基于YOLOV5+Flask安全帽RTSP视频流实时目标检测
1、背景 在现代工业和建筑行业中,安全始终是首要考虑的因素之一。特别是在施工现场,工人佩戴安全帽是确保人身安全的基本要求。然而,人工监督难免会有疏漏,尤其是在大型工地或复杂环境中,确保每个人都佩戴安全帽变得非…...
Windows内置的服务器IIS(Internet Information Services)托管网站
一. 安装IIS 打开控制面板:在开始菜单搜索“控制面板”并打开它。程序和功能:点击“程序”然后选择“程序和功能”。启用或关闭Windows功能:在左侧菜单中选择“启用或关闭Windows功能”。查找并勾选IIS:在弹出的窗口中,…...
虚幻引擎结构之UObject
一. UObject 的介绍 UObject 是虚幻引擎中的核心基础类,所有其他游戏对象和资源类都直接或间接地继承自它。作为虚幻引擎的基石,UObject 提供了多项关键功能,包括内存管理、序列化、反射(introspection)、垃圾回收以及元数据支持。在虚幻引擎中,UObject 类的实例通常被称…...
js的Reflect对象
Reflect 对象是 JavaScript ES6 中引入的一个内建对象,它提供了一系列与对象操作相关的方法。这些方法与 Object 对象上的方法类似,但在行为上有一些差异,并且更加规范和统一。Reflect 对象并不是一个构造函数,不能被 new 操作符调…...
技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
宇树科技,改名了!
提到国内具身智能和机器人领域的代表企业,那宇树科技(Unitree)必须名列其榜。 最近,宇树科技的一项新变动消息在业界引发了不少关注和讨论,即: 宇树向其合作伙伴发布了一封公司名称变更函称,因…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...
【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...
论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing
Muffin 论文 现有方法 CRADLE 和 LEMON,依赖模型推理阶段输出进行差分测试,但在训练阶段是不可行的,因为训练阶段直到最后才有固定输出,中间过程是不断变化的。API 库覆盖低,因为各个 API 都是在各种具体场景下使用。…...
Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程
鸿蒙电脑版操作系统来了,很多小伙伴想体验鸿蒙电脑版操作系统,可惜,鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机,来体验大家心心念念的鸿蒙系统啦!注意:虚拟…...
「Java基本语法」变量的使用
变量定义 变量是程序中存储数据的容器,用于保存可变的数据值。在Java中,变量必须先声明后使用,声明时需指定变量的数据类型和变量名。 语法 数据类型 变量名 [ 初始值]; 示例:声明与初始化 public class VariableDemo {publi…...
JUC并发编程(二)Monitor/自旋/轻量级/锁膨胀/wait/notify/锁消除
目录 一 基础 1 概念 2 卖票问题 3 转账问题 二 锁机制与优化策略 0 Monitor 1 轻量级锁 2 锁膨胀 3 自旋 4 偏向锁 5 锁消除 6 wait /notify 7 sleep与wait的对比 8 join原理 一 基础 1 概念 临界区 一段代码块内如果存在对共享资源的多线程读写操作…...
MeanFlow:何凯明新作,单步去噪图像生成新SOTA
1.简介 这篇文章介绍了一种名为MeanFlow的新型生成模型框架,旨在通过单步生成过程高效地将先验分布转换为数据分布。文章的核心创新在于引入了平均速度的概念,这一概念的引入使得模型能够通过单次函数评估完成从先验分布到数据分布的转换,显…...
