代码随想录算法训练营第60期第三十六天打卡
大家好!今天我们就会正式进入动态规划的章节,以前我们相继学完了回溯算法,贪心算法,今天的动态规划应该是相当重要同时也是相当难的章节,那我们废话不多说直接进入我们今天的章节。
第一部分 动态规划理论基础
那究竟什么是动态规划,如何使用动态规划算法来解决实际的题目,它会不会与贪心算法一样没有固定的模板,还有大家在动态规划里面看到的dp数组究竟是用来做什么的,带着这些疑问我们开始动态规划的理论基础章节。
动态规划中每一个状态一定是由上一个状态推导出来的,这点很重要,这里也区分贪心算法,我们的贪心算法是局部最优退出全局最优,我们接触动态规划的第一个重要问题就是背包问题,那什么是背包问题,就比如说有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。那这时候我们的dp数组就起作用了,动态规划中dp[j]是由dp[j-weight[i]]推导出来的,然后取max(dp[j], dp[j - weight[i]] + value[i])。这个强调的是状态转移,同时我们知道dp[i]数组的含义就是前i件物品的最大价值,它表示的就是最大价值,因此这或许就是我们最后的结果,这个最大值是存在于我究竟选不选第j件物品,选的话就是dp[j - weight[i]] + value[i],不选的话就是dp[j],以后到了背包问题的时候会再详细给大家讲。
接下来是我们的解题步骤,
- 确定dp数组(dp table)以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
这个我就不废话了,这个叫做动归五部曲,每一道题目我们都要按照这个思路去想,这个很重要,尤其是初始化很重要大家务必根据题目要求准确初始化。
还有一个问题就是关于debug的问题,其实就主要说一点,大家可以去一个编译器去打印dp数组,看看我们的dp数组是否正确,如果发现不正确我们就需要考虑我们找到的状态转移方程与初始化是否正确,关于理论基础我就说这么多,接下来我们就进入例题详细看看如何使用动规五部曲来解决实际的问题。
第一题对应力扣编号为509的题目斐波纳契数
这一道题目想必大家在入门递归的时候应该接触过,因为这道题目本就可以使用递归解决,不过我们了解递归算法的时间复杂度是指数级别的很慢,如果提交这道题目大概率会超时的,因此我们就可以考虑我们今天的动态规划来解决,首先根据动规五部曲,dp[i]表示的就是第i项的具体值了,但是我们差了一项,我们下标0表示第一项,接下来就是递推公式我们都知道斐波那契数列的规律就是从第三项开始后面的项等于前两项的和,接下来是初始化,这个很简单,就是前两项初始化为1就可以了,最后我们确定遍历顺序我们肯定是从前往后遍历,因为我们需要由前面的值才能推导出后面的值,那接下来我们就看一下代码:
class Solution {
public:int fib(int n) {if (n <= 1) return n;vector<int> dp(n + 1);dp[0] = 1;dp[1] = 1;for (int i = 2; i <= n; ++i){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n - 1];}
};
代码我就不解释了相信大家都可以看明白,这是动态规划的最基本的入门题目,我们就进入下一道题目。
第二题对应力扣编号为70的题目爬楼梯
我们进入今天的第二题,我们看一下题目描述:
想必大家对爬楼梯问题应该也是相当熟悉了,我们就直接按照动规五部曲来解决,首先是确定dp数组的含义,很明显我们的数组含义就是方法数,递推公式也是很简单的,就是两种方法的和,一个是走一步上来的,一个是走两步上来的,我们两种情况相加就可以,初始化这个需要注意一下,我们应该一层楼初始化为1,两层楼初始化为2,接下来我们就遍历即可,遍历顺序应该也是从前往后,因为还是前面的推导后面的,那我们就直接看一下代码:
class Solution {
public:int climbStairs(int n) {if (n <= 1) return 1;vector<int> dp(n + 1);//如果不初始化会默认dp[0] = 0但有了前面一句就不会了dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; ++i){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};
第三题对应力扣编号为746的题目使用最小花费爬楼梯
这是我们今天的最后一道题目,这道题目的确很有动态规划的感觉了,其实前面两道还是很入门的,这一道开始大家就要开始小心了,我们来看一下题目要求:
按照动规五部曲,我们首先要确定dp数组的含义,dp[i]表示到第i层楼的最少花费,随后大家在这道题目里楼梯顶部是什么意思,是要比我们cost数组多出一层的,我们cost数组只到了最高层还没到顶层,这个大家要注意,所以大家应该了解了我们最后的返回值应该是dp[cost.size()],随后就是遍历顺序很明显从前往后,还是台阶要从前面爬到后面,从底层爬到顶层才可以,接下来就是初始化的问题,这个得注意,题目说我们可以选择下标为0或者是下标为1的台阶开始所以dp[0]与dp[1]都初始化0都可以不用花费,接下来就是我们的转移方程,就是我当前的楼梯应该是前一个台阶或者是后一个台阶上来的,同时要加上花费,这样我们就可以写出代码:
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size() + 1);dp[0] = 0;dp[1] = 0;for (int i = 2; i <= cost.size(); ++i){dp[i] = min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);}return dp[cost.size()];}
};
代码我就不解释了,大家一定都可以看明白,还是状态转移的时候一定要弄清楚我们的dp数组表示的是什么,这样大家就不会不明白为什么还要加上cost的情况。其实大家只要不明白动态规划类的题目大家就需要去思考我们的dp数组表示的是什么含义。
今日总结
今天是动态规划的第一天,其实还是轻松的,以前就由基础,复习一遍就可以了,大家在以后的题目中都要按照动规五部曲的思路去解题,遇到不明白的就去思考这五步哪一步没有走好,我们明天再见!
相关文章:
代码随想录算法训练营第60期第三十六天打卡
大家好!今天我们就会正式进入动态规划的章节,以前我们相继学完了回溯算法,贪心算法,今天的动态规划应该是相当重要同时也是相当难的章节,那我们废话不多说直接进入我们今天的章节。 第一部分 动态规划理论基础 那究竟…...
Python操作MySQL 连接加入缓存层完整方案
更多内容请见: python3案例和总结-专栏介绍和目录 文章目录 1、整体架构设计2、MySQL 连接方案2.1 使用连接池 (推荐)2.2 使用 SQLAlchemy (ORM方案)3、缓存层实现方案3.1 Redis 缓存实现3.2 Memcached 缓存实现4、完整集成方案4.1 带缓存的数据库访问层4.2 使用装饰器实现缓存…...
PyTorch深度神经网络(前馈、卷积神经网络)
文章目录 神经网络概述神经元模型多层感知机前馈神经网络网络拓扑结构数学表示基本传播公式符号说明整体函数视角 卷积神经网络卷积神经网络发展简史第一代(1943-1980)第二代(1985-2006)第三代(2006-至今)快…...
现代垃圾收集器
大家好,我是你们的花姐。 话说java的长期支持版本已经发展到了JDK21,大部分同学对jvm中的垃圾收集器还停留在java8之前的CMS和G1。对java11之后引入的低延迟垃圾收集器shenandoah和zgc几乎是一无所知,甚至有同学是连这两个名字也没有听过呀,…...
Android学习总结之类LiveData与ViewModel关系篇
1. ViewModel 和 LiveData 的强依赖关系 ViewModel 和 LiveData 虽非强依赖,但在 Android 架构中常紧密协作,这基于它们的设计理念和优势互补: 数据与 UI 分离:ViewModel 的主要职责是存储和管理与 UI 相关的数据,而…...
GaussDB 实例 gsql 连接方式详解
GaussDB 实例 gsql 连接方式详解 GaussDB 是华为云推出的分布式关系型数据库服务,支持多种数据库引擎(如 MySQL、PostgreSQL、SQL Server 等)。gsql 是 GaussDB 提供的命令行客户端工具,用于连接和管理数据库实例。本文将详细介绍…...
智能体制作学习笔记2——情感客服
02 案例1-情感客服_哔哩哔哩_bilibili 目录 一、AI对视频内容总结 二、选择可代替视频总结的方案 三、豆包AI插件安装 四、通义 五、情感客服智能体制作 (一)注册 (二)进入工作空间 (三)创建智能体 (…...
部署GraphRAG配置Neo4j实现知识图谱可视化【踩坑经历】
文章目录 概要部署graphrag(一)使用conda创建虚拟环境(前提已经安装好anaconda)(二)部署graphrag 部署neo4jgraphrag生成的知识图谱导入neo4j踩坑经历1.graphrag执行graphrag index --root ./ragtest命令报错2.neo4j没有Relationship types 概要 在本地部署GraphRag࿰…...
跨域的几种方案
因为浏览器出于安全考虑,有同源策略。也就是说,如果协议、域名、端口有一个不同就是跨域,Ajax 请求会失败。 我们可以通过以下几种常用方法解决跨域的问题 JSONP JSONP 的原理很简单,就是利用 <script> 标签没有跨域限制…...
5 WPF中的application对象介绍
WPF Application 类提供了一系列生命周期事件,了解它们的触发顺序对于应用程序开发非常重要。以下是主要事件的触发顺序 1. 主要事件顺序 Startup - 应用程序启动时触发 这是第一个触发的事件 适合在此处初始化应用程序级资源 可以在此取消启动(通过设置e.Cancel = true) Act…...
Nexus首次亮相迪拜 TOKEN2049:以“手机 + 钱包 + 公链 + RWA”生态系统引领未来区块链基建
迪拜,2025年5月—— 全球 Web3 基础设施创新平台 Nexus,在本年度迪拜 TOKEN2049 全球峰会 上完成了其主网与全生态系统的首次国际公开亮相。此次参会不仅展示了 Nexus 的国际生态布局,更标志着其迈出了全球化战略关键一步。凭借对现实世界资产…...
C++ 套接字函数详细介绍
目录 头文件1. 套接字创建与配置2. 绑定地址与端口3. 连接建立4. 数据传输5. 套接字选项6. 地址转换7. 套接字关闭8. 其他实用函数 C 套接字函数详细介绍 套接字(Socket)是网络通信的基本端点,C中通常使用BSD套接字API进行网络编程。以下是主要的套接字相关函数及其…...
WordPress 和 GPL – 您需要了解的一切
如果您使用 WordPress,GPL 对您来说应该很重要,您也应该了解它。查看有关 WordPress 和 GPL 的最全面指南。 您可能听说过 GPL(通常被称为 WordPress 的权利法案),但很可能并不完全了解它。这是有道理的–这是一个复杂…...
机器人示教操作
机器人基础操作 **ES机器人试教操作知识** **1. 视角移动** **1.1 基础模式** - 关节轴控制:通过关节1至关节6实现单轴正反转移动 - 直线移动:通过X/Y/Z坐标轴沿指定方向直线移动 - 旋转移动:通过RX/RY/RZ坐标轴绕指定轴旋转 **1.2 步进模式…...
【python】UnicodeDecodeError: ‘gbk‘ codec can‘t decode byte 0xb2
报错 C:\Users\zhangbin\AppData\Local\Programs\Python\Python310\python.exe D:\XTRANS\cuda\03-graph-db\04-cmkg\pdf2zh-v1.9.9-with-assets-win64\pdf2zh\gui.py Traceback (most recent call last): File “D:\XTRANS\cuda\03-graph-db\04-cmkg\pdf2zh-v1.9.9-with-asset…...
[python] python静态方法,类方法,实例方法实现及其区别
一 静态方法 格式: 使用 staticmethmod 装饰器修饰 应用: 某个方法既不需要使用实例属性也不需要使用类属性时,就可以考虑使用静态方法 注意: 静态方法与类无关,可以被转换成函数使用,属于类本身 1.1 经典示例 创建一个与日期相关的辅助函数,这些函数不需要访问或修改类的…...
Kite AI 自动机器人部署教程
最近比较火的AI赛道,每日自动对话训练AI,赚积分 一个个用于 Kite AI 平台的自动交互机器人,支持多钱包和代理。 登记 注册链接 🌟 功能 多钱包支持(手动输入或基于文件) 代理支持(HTTP/HTTP…...
50. Pow(x, n)
50. Pow(x, n) 分治法的基本思想是将一个大问题分解成若干个相同或相似的小问题,递归地解决这些小问题,然后将这些小问题的解合并起来得到原问题的解。 class Solution:def myPow(self, x: float, n: int) -> float:# 内部定义了一个嵌套的辅助函数…...
Go 语言 sqlx 库使用:对 MySQL 增删改查
MySQL 作为目前最流行的开源关系型数据库,其 SQL 语法体系已形成行业标准,相关知识体系庞大且成熟,本文不再对 SQL 基础进行详细展开,建议尚未掌握的读者先行系统学习。本文聚焦于如何使用 Go 语言进行 MySQL 数据库操作ÿ…...
反射, 注解, 动态代理
文章目录 单元测试什么是单元测试咱们之前是如何进行单元测试的? 有啥问题 ?现在使用方法进行测试优点Junit单元测试的使用步骤删除不需要的jar包总结 反射认识反射、获取类什么是反射反射具体学什么?反射第一步:或者Class对象 获…...
继续预训练 LLM ——数据筛选的思路
GPT生成数据微调qwen-2.5多模态模型实战项目 作者:柠檬养乐多 原文地址:https://zhuanlan.zhihu.com/p/30645776656 qwen2.5-vl是阿里通义实验室推出的qwen系列最新多模态大模型,在许多指标上已经超过或接近了gpt-4o。更为方便的是࿰…...
深入解析 PostgreSQL 外部数据封装器(FDW)的 SELECT 查询执行机制
引言 PostgreSQL 中的外部数据封装器(Foreign Data Wrapper, FDW)是一种扩展,允许您像访问 PostgreSQL 数据库中的表一样,访问和操作存储在外部数据源中的数据。FDW 使 PostgreSQL 能够与多种数据存储系统(包括关系型…...
数据库系统概论|第六章:关系数据理论—课程笔记2
前言 前文我们介绍了规划化的基本概念,同时引入了关于规范化的相关定义与基本概念,低一级范式的关系模式,通过模式分解,可以转换为若干个高一级范式的关系模式的集合,这种过程就叫规范化。本文将围绕范式展开讨论&…...
package-lock.json能否直接删除?
package-lock.json能否直接删除? package-lock.json 生成工具:由 npm 自动生成。 触发条件:当运行 npm install 时,如果不存在 package-lock.json,npm 会创建它;如果已存在,npm 会根据它精确安…...
Ubuntu磁盘空间分析:du命令及常用组合
1、du命令的作用 du(Disk Usage)是 Ubuntu 系统中用于查看目录或文件磁盘使用情况的命令,主要用于分析磁盘空间占用。 2、语法 du [选项] [目录/文件路径]常用选项 2.1、-h 以 KB、MB、GB 等人性化可读格式(Human-readable&am…...
《数据库原理》部分习题解析1
《数据库原理》部分习题解析1 1. 名词解释 (1)关系(2)属性(3)域(4)元组(5)码(6)分量(7)关系模式 ࿰…...
汇川Easy系列PLC数据值改变功能块(随动增益改变判断)
PLC值改变事件 值改变触发功能块 PLC值改变事件 值改变触发功能块(SCL ST完整源代码)-CSDN博客文章浏览阅读1.1k次。本文介绍了在PLC中处理值改变事件的方法,包括值改变触发功能块的实现,详细讲解了FB接口定义、ST代码,并提供了在博途平台上的实现。此外,还分享了如何利用…...
数据清洗的艺术:如何为AI模型准备高质量数据集?
数据清洗的艺术:如何为AI模型准备高质量数据集? 引言 在人工智能和机器学习领域,我们常常听到"垃圾进,垃圾出"(Garbage in, garbage out)这句格言。无论你的模型架构多么精妙,算法多么先进,如果…...
怎么查看当前vue项目,要求的node.js版本
怎么查看当前vue项目,要求的node.js版本 找到 package.json package-lock.json 搜索 node...
游戏引擎学习第278天:将实体存储移入世界区块
总结并为今天的内容做好铺垫 今天的内容是关于开发一个完整的实体系统,目标是让这个系统更加实际和有效。之前讨论了如何通过一个模拟区域来处理无限大的世界。最初,使用浮动点数而不是双精度浮点数来避免潜在的精度问题,因为一些平台&#…...
计算机组成与体系结构:缓存设计概述(Cache Design Overview)
目录 Block Placement(块放置) Block Identification(块识别) Block Replacement(块替换) Write Strategy(写策略) 总结: 高速缓存设计包括四个基础核心概念…...
在Linux中如何使用Kill(),向进程发送发送信号
kill()函数 #include <sys/types.h> #include <signal.h> int kill(pid_t pid, int sig); 函数参数和返回值含义如下: pid:参数 pid 为正数的情况下,用于指定接收此信号的进程 pid;除此之外,参数 pid 也可设置为 0 或-1 以及小于-1 等不同值,稍后给说明。 …...
ElasticSearch重启之后shard未分配问题的解决
以下是Elasticsearch重启后分片未分配问题的完整解决方案,结合典型故障场景与最新实践: 一、快速诊断定位 检查集群状态 GET /_cluster/health?pretty # status为red/yellow时需关注unassigned_shards字段值 2.查看未分配分片详情 …...
基于 Spring Boot 瑞吉外卖系统开发(十四)
基于 Spring Boot 瑞吉外卖系统开发(十四) 查询订单 在管理端的首页,单击左侧菜单栏中的“订单明细”,会在右侧打开订单明细页面。 请求路径:/order/page 请求方法:GET 参数:page pageSize …...
【软件测试】第二章·软件测试的基本概念
🌈 个人主页:十二月的猫-CSDN博客 🔥 系列专栏:🏀软件测试与软件项目管理_十二月的猫的博客-CSDN博客 💪🏻 十二月的寒冬阻挡不了春天的脚步,十二点的黑夜遮蔽不住黎明的曙光 目录 …...
部署安装gitlab-ce-17.9.7-ce.0.el8.x86_64.rpm
目录 编辑 实验环境 所需软件 实验开始 安装部署gitlab171.配置清华源仓库(版本高的系统无需做)vim /etc/yum.repos.d/gitlab-ce.repo 2.提前下载包dnf localinstall gitlab-ce-17.9.7-ce.0.el8.x86_64.rpm --rocklinux 3.修改配…...
2025五一杭州西湖三天游
2025五一杭州西湖三天游 文章目录 2025五一杭州西湖三天游一、前言二、杭州游玩记录三、杭州三日游小结四、杭州美食街1、河坊街2、胜利河美食街3、高银街4、中山南路美食街5、武林夜市6、啦喜街美食广场7、大兜路美食街 五、豆包推荐的杭州三日游攻略三天主要行程**第一天&…...
实验五:以太网UDP全协议栈的实现(通过远程实验系统)
文章目录 FPGA以太网:从ARP到UDP的完整协议栈一、引言二、核心模块详解1. ARP协议处理模块1.1 `arp_cache`:ARP缓存模块1.2 `arp_tx`:ARP请求与应答发送模块1.3 `arp_rx`:ARP接收与解析模块2. MAC层处理模块2.1 `mac_layer`:MAC层顶层模块2.2 `mac_tx_mode`:MAC发送模式选…...
现代计算机图形学Games101入门笔记(八)
三角形三点已经知道在uv的位置了,那三角形内部的点,怎么算。 先看A 任一点 面积比求 根据三点坐标属性差值出内部点的位置。 纹理太小了,映射处理方式,取邻近的Nearest感觉一格格的,取周围4个权重Bilinear,取4*4Bicubi…...
C语言学习之文件操作
经过前面的学习,我们已经基本掌握了如何去写一个C语言的代码了。但是在实际的项目中,我们不可能不需要文件去操作。因为如果没有文件,我们写的程序是存储在电脑的内存中的。如果程序推出,内存回收数据就随之丢失了。如果我们要对数…...
《AI大模型应知应会100篇》第63篇:AutoGPT 与 BabyAGI:自主代理框架探索
第63篇:AutoGPT 与 BabyAGI:自主代理框架探索 摘要 随着大语言模型(LLM)技术的不断演进,自主代理(Autonomous Agent) 正在成为 AI 应用的新范式。它不仅能够理解用户意图,还能自主规…...
使用大模型预测急性结石性疾病技术方案
目录 1. 数据预处理与特征工程伪代码 - 数据清洗与特征处理数据预处理流程图2. 大模型构建与训练伪代码 - 模型训练模型训练流程图3. 术前预测系统伪代码 - 术前风险评估术前预测流程图4. 术中实时调整系统伪代码 - 术中风险预警术中调整流程图5. 术后护理系统伪代码 - 并发症预…...
基于运动补偿的前景检测算法
这段代码实现了基于运动补偿的前景检测算法。 主要功能包括: 运动补偿模块:使用基于网格的 KLT 特征跟踪算法计算两帧之间的运动,然后通过单应性变换实现帧间运动补偿。前景检测模块:结合两帧运动补偿结果,通过帧间差…...
鸿蒙OSUniApp开发富文本编辑器组件#三方框架 #Uniapp
使用UniApp开发富文本编辑器组件 富文本编辑在各类应用中非常常见,无论是内容创作平台还是社交软件,都需要提供良好的富文本编辑体验。本文记录了我使用UniApp开发一个跨平台富文本编辑器组件的过程,希望对有类似需求的开发者有所启发。 背景…...
W5500使用SocketTool工具测试
W5500使用SocketTool工具测试 1、按“WINR” 2、输入“IPCONFIG”,得到计算机的IP地址,子网掩码和网关 3、设置W5500设备网络参数如下: 本地网关:192.168.1.1 本地子网掩码: 255.255.255.0 本地物理地址:0C 2…...
《Python星球日记》 第71天:命名实体识别(NER)与关系抽取
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 目录 一、命名实体识别(NER)基础1. 什么是命名实体识别&#…...
双向长短期记忆网络-BiLSTM
5月14日复盘 二、BiLSTM 1. 概述 双向长短期记忆网络(Bi-directional Long Short-Term Memory,BiLSTM)是一种扩展自长短期记忆网络(LSTM)的结构,旨在解决传统 LSTM 模型只能考虑到过去信息的问题。BiLST…...
CentOS7原有磁盘扩容实战记录(LVM非LVM)【针对GPT分区】
一、环境 二、命令及含义 fdisk fdisk是一个较老的分区表创建和管理工具,主要支持MBR(Master Boot Record)格式的分区表。MBR分区表支持的硬盘单个分区最大容量为2TB,最多可以有4个主分区。fdisk通过命令行界面进行操…...
如何在终端/命令行中把PDF的每一页转换成图片(PNG)
今天被对象安排了一个任务: 之前自己其实也有这个需要,但是吧,我懒:量少拖拽,量大就放弃。但这次躲不过去了,所以研究了一下有什么工具可以做到这个需求。 本文记录我这次发现的使用 XpdfReader 的方法。…...
【0415】Postgres内核 释放指定 memory context 中所有内存 ④
1. frees all memory (memory context) Postgres内核中由函数 AllocSetReset() 完成该功能。即 “释放给定set中分配的所有内存。” 它应当将所有已分配的chunks标记为已释放,但不一定需要归还set所拥有的全部资源。我们的实际实现是,除了“保留”块(“keeper” block)(…...