当前位置: 首页 > 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 操作符调…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...