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

Studying-代码随想录训练营day33| 动态规划理论基础、509.斐波那契函数、70.爬楼梯、746.使用最小花费爬楼梯

第33天,动态规划开始,新的算法💪(ง •_•)ง,编程语言:C++

目录

动态规划理论基础

动态规划的解题步骤

动态规划包含的问题

动态规划如何debug

509.斐波那契函数

70.爬楼梯 

746.使用最小花费爬楼梯

总结 


动态规划理论基础

文档讲解:代码随想录动态规划理论基础

动态规划(Dynamic Programming),简称DP,通常用以解决某一问题有很多子问题的情况。

动态规划中每一个状态一定是由上一个状态推导出来的,这一点区别于贪心,贪心没有状态推导,而是从局部直接选出最优。

以背包问题为例,有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大?

在动态规划中dp[j]是由dp[j-weight[i]]推导出来的,然后取max(dp[j], dp[j - weight[i]] + value[i])。而贪心则是每次拿物品选一个最大的或者最小的就完事了,和上一个状态没有关系。所以贪心是解决不了动态规划的问题的。

动态规划的解题步骤

动态规划中,最重要的一个部分是状态转移公式,也即递推公式。但找到递推公式也只是一方面,我们在解题的时候,还需要构造dp数组,我们还需要确定dp数组中下标表示的含义,这样才能够有助于我们真正理解题目。

对于动态规划问题,我们可以把解题步骤拆解为如下五步:

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

解题过程中,依据上述5步进行。注意对dp数组的初始化,是在确定递推公式后的,因为有些初始化是要依据递推公式进行的。

动态规划包含的问题

动态规划一般包含的问题有:

  • 基础题目
  • 背包问题
  • 打家劫舍
  • 股票问题
  • 子序列问题

动态规划是一个很大的领域,对于后面的每一种问题,还需要进行单独的讲解。

动态规划如何debug

我们在解动态规划问题时,如果出现无法通过的时候,一定不要慌张,代码出现问题是很正常的。我们最重要的是不能让代码对我们而言是黑盒状态,就是我们都不确定它的运行顺序和结果。

最好的debug方式,就是把dp数组打印出来,看看结果究竟是不是按照自己思路推导的,又是哪一个部分出了错误。

同时做动规的题目,写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍,心中有数,确定最后推出的是想要的结果

在对动态规划问题进行debug时,我们一定要牢记三个问题:

  • 这道题目我举例推导状态转移公式了么?
  • 我打印dp数组的日志了么?
  • 打印出来了dp数组和我想的一样么?

牢记上述三个问题,基本就能够解决动态规划解题过程中遇到的问题。 


509.斐波那契函数

文档讲解:代码随想录斐波那契函数

视频讲解:手撕斐波那契函数

题目:

学习:本题是非常经典的数学题目之一,也是标准的动态规划题目。递推公式在题干中就已经给了我们,剩下的就是我们依照动规五部曲,逐步进行。

1.确定dp数组以及下标的含义:在这里我们可以定义一个vector型的dp数组,dp[i]定义为第i个斐波那契数值。

2.确定递推公式,dp[i] = dp[i - 1] + dp[i - 2]

3.dp数组初始化:根据递推公式我们知道,至少要有两个数,才能够递推下去。因此我们需要初始化dp[0] = 0; dp[1] = 1;

4.确定遍历顺序:从递归公式中,我们发现dp[i]是依赖于dp[i - 1]和dp[i - 2]的,因此遍历顺序一定要从前往后进行遍历。

5.举例推导dp数组:我可以依照我们上述构造的dp数组和递推关系,当n = 10时,dp数组应该为:0,1,1,2,3,5,8,13,21,34,55。如果发现结果不对,我们也可以通过打印dp数组来查看问题出在哪。

代码:

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:int fib(int n) {//动态规划,使用dp数组,存储斐波那契数列数值if(n < 2) return n; //0,1单独处理vector<int> dp(n + 1); //从0-N,dp(n)表示第n个数的斐波那契数值dp[0] = 0;dp[1] = 1;for(int i = 2; i <= n; i++){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};

代码:对于本题来说,实际上也可以不适用dp数组,我们只需要维护两个值就可以了

//时间复杂度O(n)
//空间复杂度O(1)
class Solution {
public:int fib(int n) {//动态规划,不使用dp数值,只找到第n个值if(n < 2) return n;int dp0 = 0;int dp1 = 1;int sum;for(int i = 2; i <= n; i++) {sum = dp0 + dp1;dp0 = dp1;dp1 = sum;}return dp1;}
};

代码:本题还可以使用递推公式进行,代码极度简便,但并不好想。

//时间复杂度O(2^n)
//空间复杂度O(n)
class Solution {
public:int fib(int n) {//递归法,非常恐怖if(n < 2) return n;else return fib(n - 1) + fib(n - 2);}
};

70.爬楼梯 

文档讲解:代码随想录爬楼梯

视频讲解:手撕爬楼梯

题目:

学习:本题实际上是斐波那契数的变种,递推公式都是一样的。这也可见动态规划问题能够想出递推公式确认是十分重要的。

对于本题来说,由于一次可以爬1或2个台阶,因此对于第3层台阶来说,可以从第一层爬2层台阶到达,也可以从第二层爬1层台阶到达。而到达第一层和第二层的种类分别是dp[1]和dp[2]因此,到达第三层的种类就为dp[1]+dp[2],之后的第四层也是如此,能够通过从第二层爬2阶到达,也能够通过从第三层爬1阶到达……

最后就能够得到同样的递推公式dp[n] = dp[n - 1] + dp[n - 2]。但要注意本题中与斐波那契数不同的式dp[0]在本题中是没有意义的,虽然我们给dp[0]赋值为1(因为dp[2]=2)也能够解决问题,但是dp[0]是没有实际意义的,因此本题更推荐给dp[1]和dp[2]进行初始化。

代码:

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:int climbStairs(int n) {//动态规划//1.确定dp数组以及下标的含义vector<int> dp(n + 1); //dp(n)表示爬n阶的方法//2.确定递归条件:dp(n) = dp(n - 1) + dp(n - 2);//3.dp数组初始化,因为dp(0)是没有意义的,且n也不会等于0,因此不需要初始化0if(n <= 1) return n;dp[1] = 1;dp[2] = 2;//4.确定遍历顺序for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];//5.举例推导dp数组(打印dp数组)//cout << dp[i] << endl;}return dp[n];}
};

746.使用最小花费爬楼梯

文档讲解:代码随想录使用最小花费爬楼梯

视频讲解:手撕使用最小花费爬楼梯

题目:

学习:本题我们需要注意题干中的两个点:1.cost[i],是从i个台阶向上爬需要支付的费用,也就是我们只有向上爬了,才需要支付费用,我们站在i台阶上,是不需要支付cost[i]的。2.到达楼梯顶部不是指第最后的下标(cost.size() - 1)个台阶,实际上根据例子我们可以发现,是最后一个台阶还要再上一个台阶才是顶部的位置。

基于此,我们可以通过递归五部曲来求解本题。

1.确定dp数组以及下标的含义:我们可以构造一个vector型dp数组,其中dp[i]应该定义为到达第i个台阶所花费的最小体力,这样我们最后求出的dp[cost.size()]才是到达顶部的花费最小体力。

2.确定递推公式:对于第i个台阶来说,有两个途径能够得到dp[i],一个是dp[i - 1],一个是dp[i - 2]而我们需要得到最小的,因此dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])。

3.初始化dp数组:通过递推公式我们知道,至少需要两个数才能够推出后面的值,因此我们可以初始化dp[0] 和 dp[1](注意本题中题干给出了0下标的含义)

4.确定遍历顺序:显然本题也是从前往后进行遍历。

5.举例推导dp数组:

代码:

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {//动态规划//1.确定dp数组及下标含义vector<int> dp(cost.size() + 1); //dp[n]表示上到第n个台阶所要消耗的最小花费//2.确定递推公式 dp[n] = min(dp[n - 1] + cost[n - 1], dp[n - 2] + cost[n - 2]);//3.dp数组初始化(规定cost.size() >= 2)dp[0] = 0; //爬的时候才消耗费用dp[1] = 0;//4.确定遍历顺序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()];}
};

总结 

动态规划开始,牢记动态五部曲,做题不慌张。

相关文章:

Studying-代码随想录训练营day33| 动态规划理论基础、509.斐波那契函数、70.爬楼梯、746.使用最小花费爬楼梯

第33天&#xff0c;动态规划开始&#xff0c;新的算法&#x1f4aa;(ง •_•)ง&#xff0c;编程语言&#xff1a;C 目录 动态规划理论基础 动态规划的解题步骤 动态规划包含的问题 动态规划如何debug 509.斐波那契函数 70.爬楼梯 746.使用最小花费爬楼梯 总结 动态…...

【康复学习--LeetCode每日一题】724. 寻找数组的中心下标

题目&#xff1a; 给你一个整数数组 nums &#xff0c;请计算数组的 中心下标 。 数组 中心下标 是数组的一个下标&#xff0c;其左侧所有元素相加的和等于右侧所有元素相加的和。 如果中心下标位于数组最左端&#xff0c;那么左侧数之和视为 0 &#xff0c;因为在下标的左侧不…...

LeetCode-刷题记录-前缀和合集(本篇blog会持续更新哦~)

一、前缀和&#xff08;Prefix Sum&#xff09;算法概述 前缀和算法通过预先计算数组的累加和&#xff0c;可以在常数时间内回答多个区间和相关的查询问题&#xff0c;是解决子数组和问题中的重要工具。 它的基本思想是通过预先计算和存储数组的前缀和&#xff0c;可以在 O(1)…...

【中项第三版】系统集成项目管理工程师 | 第 4 章 信息系统架构③ | 4.6

前言 第4章对应的内容选择题和案例分析都会进行考查&#xff0c;这一章节属于技术相关的内容&#xff0c;学习要以教材为准。本章分值预计在4-5分。 目录 4.6 网络架构 4.6.1 基本原则 4.6.2 局域网架构 4.6.3 广域网架构 4.6.4 移动通信网架构 4.6.5 软件定义网络 4.6…...

知识图谱入门笔记

自学参考&#xff1a; 视频&#xff1a;斯坦福CS520 | 知识图谱 最全知识图谱综述 详解知识图谱的构建全流程 知识图谱构建&#xff08;概念&#xff0c;工具&#xff0c;实例调研&#xff09; 一、基本概念 知识图谱&#xff08;Knowledge graph&#xff09;&#xff1a;由结…...

常见的气体流量计有哪些?

1.气体涡轮流量计 适用场合&#xff1a;流量变化小&#xff0c;脉动流频率小&#xff0c;中低压洁净天然气优点 1.精度高&#xff0c;重复性好 2.测量范围广&#xff0c;压损小&#xff0c;安装维修方便 3.具有较高的抗电磁干扰和抗震动能力缺点&#xff1a;分辨率低&#xff…...

AI推介-大语言模型LLMs论文速览(arXiv方向):2024.07.01-2024.07.05

文章目录&#xff5e; 1.LLM Internal States Reveal Hallucination Risk Faced With a Query2.Fine-Tuning with Divergent Chains of Thought Boosts Reasoning Through Self-Correction in Language Models3.Investigating Decoder-only Large Language Models for Speech-t…...

Android IP地址、子网掩码、默认网关、首选DNS服务器、备用DNS服务器校验

Android IP地址、子网掩码、默认网关、首选DNS服务器、备用DNS服务器校验 public String isIP(String ip) {String regex = "(25[0-5]|2[0-4]\\d|1\\d{2}|[1-9]?\\d)(\\.(25[0-5]|2[0-4]\\d|1\\d{2}|[1-9]?\\d)){3}";Pattern p = Pattern.compile(regex)...

铁威马NAS教程丨为什么修复文件系统、为卷扩容、增加及删除 SSD 缓存等操作失败?

适用机型&#xff1a; 所有 TNAS 型号 适用版本&#xff1a; 所有 TOS 版本 问题现象&#xff1a; 在尝试修复文件系统、为卷扩容、增加或删除 SSD 缓存时(TOS 5)&#xff0c;可能因卷被其他进程占用而操作失败。 解决方法&#xff1a; 为了成功执行上述操作&#xff0c;您…...

【深度学习】第3章——回归模型与求解分析

一、回归分析 1.定义 分析自变量与因变量之间定量的因果关系&#xff0c;根据已有的数据拟合出变量之间的关系。 2.回归和分类的区别和联系 3.线性模型 4.非线性模型 5.线性回归※ 面对回归问题&#xff0c;通常分三步解决 第一步&#xff1a;选定使用的model&#xff0c;…...

Maven的基本使用

引入依赖 1.引入Maven仓库存在的依赖&#xff0c;直接引入&#xff0c;刷新Maven <dependency><groupId>org.springframework</groupId><artifactId>spring-webmvc</artifactId><version>5.2.12.RELEASE</version> </dependency…...

【笔记】finalshell中使用nano编辑器GNU

ctrl O 保存 enter 确定 ctrl X 退出 nano编辑 能不用就不用吧 因为我真用不习惯 nano编辑的文件也可以用vim编辑的...

markdown文件转pdf

步骤&#xff1a;md转html转pdf pom引入 <!--markdown 转pdf--><dependency><groupId>com.vladsch.flexmark</groupId><artifactId>flexmark-all</artifactId><version>0.64.8</version></dependency><dependency&g…...

课设:二手车交易管理系统(Java+MySQL)

简易数据库课程设计~分享 技术栈 本项目使用以下技术栈构建&#xff1a; Java: 作为主要编程语言&#xff0c;负责业务逻辑的实现。MySQL: 用于数据存储&#xff0c;管理用户、车辆和订单信息。JDBC: 用于Java与MySQL数据库之间的连接和操作。Swing GUI: 提供用户图形界面&am…...

vue3实现无缝滚动 列表滚动 vue3-seamlessscroll

vue3框架内使用无缝滚动&#xff0c;使用一个插件比较合适&#xff08;gitee地址&#xff09;&#xff1a; vue3-seamless-scroll: Vue3.0 无缝滚动组件 具体更多配置请看&#xff1a; 组件配置 | vue3-scroll-seamless 1. 安装&#xff1a; npm install vue3-seamless-sc…...

Python酷库之旅-第三方库Pandas(012)

目录 一、用法精讲 28、pandas.HDFStore.keys函数 28-1、语法 28-2、参数 28-3、功能 28-4、返回值 28-5、说明 28-6、用法 28-6-1、数据准备 28-6-2、代码示例 28-6-3、结果输出 29、pandas.HDFStore.groups函数 29-1、语法 29-2、参数 29-3、功能 29-4、返回…...

SpringCloud集成nacos之jasypt配置中心的密码加密的自动解密

目录 1.引入相关的依赖 2.nacos的yaml的相关配置&#xff0c;配置密码和相关算法 3.配置数据源连接 3.1 数据库连接配置 4.连接数据库配置类详解&#xff08;DataSourceConfig&#xff09;。 5.完整的配置类代码如下 1.引入相关的依赖 <dependency><groupId>…...

Python 中将字典内容保存到 Excel 文件使用详解

概要 在数据处理和分析的过程中,经常需要将字典等数据结构保存到Excel文件中,以便于数据的存储、共享和进一步分析。Python提供了丰富的库来实现这一功能,其中最常用的是pandas和openpyxl。本文将详细介绍如何使用这些库将字典内容保存到Excel文件中,并包含具体的示例代码…...

libaom 编码器 aomenc 使用文档介绍

使用方法&#xff1a;./aomenc <选项> -o 目标文件名 源文件名 使用 --help 查看完整的选项列表。 选项&#xff1a; --help 显示使用选项并退出-c <参数>, --cfg<参数> 使用配置文件-D, --debug 调试模式&#xff08;使输出确定性&#xff09;-o <参数&g…...

速盾:cdn 缓存图片

现如今&#xff0c;互联网已经成为我们日常生活中不可或缺的一部分。在我们使用互联网时&#xff0c;经常会遇到图片加载缓慢、文章打开慢等问题。为了解决这些问题&#xff0c;CDN&#xff08;内容分发网络&#xff09;应运而生。CDN 是一种通过将数据缓存在世界各地的服务器上…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

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…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...

macOS 终端智能代理检测

&#x1f9e0; 终端智能代理检测&#xff1a;自动判断是否需要设置代理访问 GitHub 在开发中&#xff0c;使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新&#xff0c;例如&#xff1a; fatal: unable to access https://github.com/ohmyzsh/oh…...

DAY 26 函数专题1

函数定义与参数知识点回顾&#xff1a;1. 函数的定义2. 变量作用域&#xff1a;局部变量和全局变量3. 函数的参数类型&#xff1a;位置参数、默认参数、不定参数4. 传递参数的手段&#xff1a;关键词参数5 题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一…...