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

代码随想录算法训练营第51期第32天 | 理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

理论基础

动态规划:dp,每一个状态都是由上个状态推导出来的,因为我是先写完三道题再看理论的,所以有点感概;

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

509. 斐波那契数

509. 斐波那契数icon-default.png?t=O83Ahttps://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. 爬楼梯icon-default.png?t=O83Ahttps://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. 使用最小花费爬楼梯icon-default.png?t=O83Ahttps://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. 使用最小花费爬楼梯

理论基础 动态规划&#xff1a;dp&#xff0c;每一个状态都是由上个状态推导出来的&#xff0c;因为我是先写完三道题再看理论的&#xff0c;所以有点感概&#xff1b; 确定dp数组&#xff08;dp table&#xff09;以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举…...

爱思唯尔word模板

爱思唯尔word模板 有时候并不一定非得latex https://download.csdn.net/download/qq_38998213/90199214 参考文献书签链接...

每日一题 354. 俄罗斯套娃信封问题

354. 俄罗斯套娃信封问题 需要对信封排序 ,重点是再宽度相同时&#xff0c;逐步减少其高度 class Solution { public:int maxEnvelopes(vector<vector<int>>& envelopes) {sort(envelopes.begin(),envelopes.end(),[](const vector<int>&a,const v…...

ASP.net网站的注册、登录和密码修改的操作详解

一、进入注册、登录和密码修改操作详解 ASP.net网站为用户提供不同权限状态下的操作界面。根据用户登录状态&#xff0c;页面会显示不同的选项。 已登录用户的操作 图1 登录后操作界面 当用户已登录系统时&#xff0c;会显示以下内容和功能&#xff1a; 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 因其易用性、动态计算图和高效性而日益流行&#xff0c;成为实现深度学习模型的首选。如果你想探索这个工具并学习如何在 Ubuntu 上安装 PyTorch&#xff0c;本指南将对你有所帮助&#xff01; 在本教程中&#xff0c;我们将引导你完成在 Ubuntu 系统上使用 Pip…...

8-Gin 中间件 --[Gin 框架入门精讲与实战案例] 【文末有测试代码】

路由中间件 Gin 是一个用 Go (Golang) 编写的 HTTP web 框架。它以性能好、中间件支持灵活著称&#xff0c;非常适合用来构建微服务或 RESTful API 服务。下面我将提供三个使用 Gin 的路由中间件的完整示例。 示例 1: 简单的日志记录中间件 这个中间件会在每个请求处理前后打…...

【潜意识Java】深入详细理解分析Java中的toString()方法重写完整笔记总结,超级详细。

目录 一、toString() 方法是啥&#xff1f; &#xff08;一&#xff09;默认的 toString() 方法 &#xff08;二&#xff09;toString() 方法的作用 二、为啥要重写 toString() 方法&#xff1f; &#xff08;一&#xff09;提高代码的可读性 &#xff08;二&#xff09;…...

【论文笔记】Contrastive Learning for Sign Language Recognition and Translation

&#x1f34e;个人主页&#xff1a;小嗷犬的个人主页 &#x1f34a;个人网站&#xff1a;小嗷犬的技术小站 &#x1f96d;个人信条&#xff1a;为天地立心&#xff0c;为生民立命&#xff0c;为往圣继绝学&#xff0c;为万世开太平。 基本信息 标题: Contrastive Learning for…...

Gitlab17.7+Jenkins2.4.91实现Fastapi/Django项目持续发布版本详细操作(亲测可用)

一、gitlab设置&#xff1a; 1、进入gitlab选择主页在左侧菜单的下面点击管理员按钮。 2、选择左侧菜单的设置&#xff0c;选择网络&#xff0c;在右侧选择出站请求后选择允许来自webhooks和集成对本地网络的请求 3、webhook设置 进入你自己的项目选择左侧菜单的设置&#xff…...

一起来看--红黑树

【欢迎关注编码小哥&#xff0c;学习更多实用的编程方法和技巧】 红黑树是一种自平衡的二叉搜索树&#xff0c;广泛应用于计算机科学中&#xff0c;尤其是在实现关联数组和集合时。它的设计旨在确保在最坏情况下&#xff0c;基本动态集合操作&#xff08;如插入、删除和查找&am…...

SpringBoot整合篇 05、Springboot整合Redission

文章目录 前言Redission详细配置步骤pom依赖application.yaml配置类CacheConfigEnvironmentContext RedissionController单测 前言 本篇博客是SpringBoot整合Redission&#xff0c;若文章中出现相关问题&#xff0c;请指出&#xff01; 所有博客文件目录索引&#xff1a;博客…...

供应链系统设计-供应链中台系统设计(六)- 商品中心概念篇

概述 我们在供应链系统设计-中台系统设计系列&#xff08;五&#xff09;- 供应链中台实践概述 中描述了什么是供应链中台&#xff0c;供应链中台主要包含了那些组成部门。包括业务中台、通用中台等概念。为了后续方便大家对于中台有更深入的理解&#xff0c;我会逐一针对中台…...

胡闹厨房练习(三)

ScriptableObject 一、初步了解 1、实质:是一种特殊类型的Unity对象, 2、作用:用于存储大量数据,而不必依附于游戏场景中的某个GameObject。 3、特点: 可以在不增加场景中对象数量的情况下,管理和存储复杂的数据结构、配置信息、游戏状态等。 4、适用:非常适合用来…...

关于ESD(静电放电)等级的划分

关于ESD&#xff08;静电放电&#xff09;等级的划分&#xff0c;主要依据不同的测试模型和测试标准。以下是对HBM&#xff08;人体模型&#xff09;和CDM&#xff08;充电器件模型&#xff09;两种测试模型下ESD等级划分的详细解释&#xff1a; HBM ESD等级划分 HBM ESD等级…...

探究步进电机与输入脉冲的关系

深入了解步进电机 前言一、 步进电机原理二、 细分三、脉冲数总结 前言 主要是探究以下内容&#xff1a; 1、步进电机的步进角。 2、什么是细分。 3、脉冲的计算。 最后再扩展以下STM32定时器的计算方法。 一、 步进电机原理 其实语言描述怎么样都不直观&#xff0c;我更建议…...

基于YOLOV5+Flask安全帽RTSP视频流实时目标检测

1、背景 在现代工业和建筑行业中&#xff0c;安全始终是首要考虑的因素之一。特别是在施工现场&#xff0c;工人佩戴安全帽是确保人身安全的基本要求。然而&#xff0c;人工监督难免会有疏漏&#xff0c;尤其是在大型工地或复杂环境中&#xff0c;确保每个人都佩戴安全帽变得非…...

Windows内置的服务器IIS(Internet Information Services)托管网站

一. 安装IIS 打开控制面板&#xff1a;在开始菜单搜索“控制面板”并打开它。程序和功能&#xff1a;点击“程序”然后选择“程序和功能”。启用或关闭Windows功能&#xff1a;在左侧菜单中选择“启用或关闭Windows功能”。查找并勾选IIS&#xff1a;在弹出的窗口中&#xff0c…...

虚幻引擎结构之UObject

一. UObject 的介绍 UObject 是虚幻引擎中的核心基础类,所有其他游戏对象和资源类都直接或间接地继承自它。作为虚幻引擎的基石,UObject 提供了多项关键功能,包括内存管理、序列化、反射(introspection)、垃圾回收以及元数据支持。在虚幻引擎中,UObject 类的实例通常被称…...

js的Reflect对象

Reflect 对象是 JavaScript ES6 中引入的一个内建对象&#xff0c;它提供了一系列与对象操作相关的方法。这些方法与 Object 对象上的方法类似&#xff0c;但在行为上有一些差异&#xff0c;并且更加规范和统一。Reflect 对象并不是一个构造函数&#xff0c;不能被 new 操作符调…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...