代码随想录算法训练营第32天 动态规划part01| 题目:理论基础 、 509. 斐波那契数 、70. 爬楼梯 、 746. 使用最小花费爬楼梯

代码随想录算法训练营第32天 动态规划part01| 题目:理论基础 、 509. 斐波那契数 、70. 爬楼梯 、 746. 使用最小花费爬楼梯

文章来源:代码随想录
理论

题目名称:509. 斐波那契数

斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n > 1 给你n ,请计算 F(n) 。

示例 1:

输入:2
输出:1
解释:F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2:

输入:3
输出:2
解释:F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3:

输入:4
输出:3
解释:F(4) = F(3) + F(2) = 2 + 1 = 3
提示:

0 <= n <= 30

第一想法:

简单的模拟就可以解决,重要是要体现dp的步骤

解答思路:

斐波那契数列大家应该非常熟悉不过了,非常适合作为动规第一道题目来练练手。

因为这道题目比较简单,可能一些同学并不需要做什么分析,直接顺手一写就过了。

但「代码随想录」的风格是:简单题目是用来加深对解题方法论的理解的。

通过这道题目让大家可以初步认识到,按照动规五部曲是如何解题的。

对于动规,如果没有方法论的话,可能简单题目可以顺手一写就过,难一点就不知道如何下手了。

所以我总结的动规五部曲,是要用来贯穿整个动态规划系列的,就像之前讲过二叉树系列的递归三部曲 (opens new window),回溯法系列的回溯三部曲 (opens new window)一样。后面慢慢大家就会体会到,动规五部曲方法的重要性。

#动态规划
动规五部曲:

这里我们要用一个一维dp数组来保存递归的结果

1.确定dp数组以及下标的含义
dp[i]的定义为:第i个数的斐波那契数值是dp[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];中可以看出,dp[i]是依赖 dp[i - 1] 和 dp[i - 2],那么遍历的顺序一定是从前到后遍历的

5.举例推导dp数组
按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2],我们来推导一下,当N为10的时候,dp数组应该是如下的数列:

0 1 1 2 3 5 8 13 21 34 55

如果代码写出来,发现结果不对,就把dp数组打印出来看看和我们推导的数列是不是一致的。

时间复杂度:O(n)
空间复杂度:O(n)
当然可以发现,我们只需要维护两个数值就可以了,不需要记录整个序列。

收获:

题目名称:70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

示例 1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1 阶 + 1 阶
2 阶
示例 2:

输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶

第一想法:

首先1. dp[i]是第i个楼梯到达的方法数

解答思路:

本题大家如果没有接触过的话,会感觉比较难,多举几个例子,就可以发现其规律。

爬到第一层楼梯有一种方法,爬到二层楼梯有两种方法。

那么第一层楼梯再跨两步就到第三层 ,第二层楼梯再跨一步就到第三层。

所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来,那么就可以想到动态规划了。

我们来分析一下,动规五部曲:

定义一个一维数组来记录不同楼层的状态

1.确定dp数组以及下标的含义
dp[i]: 爬到第i层楼梯,有dp[i]种方法

2.确定递推公式
如何可以推出dp[i]呢?

从dp[i]的定义可以看出,dp[i] 可以有两个方向推出来。

首先是dp[i - 1],上i-1层楼梯,有dp[i - 1]种方法,那么再一步跳一个台阶不就是dp[i]了么。

还有就是dp[i - 2],上i-2层楼梯,有dp[i - 2]种方法,那么再一步跳两个台阶不就是dp[i]了么。

那么dp[i]就是 dp[i - 1]与dp[i - 2]之和!

所以dp[i] = dp[i - 1] + dp[i - 2] 。

在推导dp[i]的时候,一定要时刻想着dp[i]的定义,否则容易跑偏。

这体现出确定dp数组以及下标的含义的重要性!

3.dp数组如何初始化
再回顾一下dp[i]的定义:爬到第i层楼梯,有dp[i]种方法。

那么i为0,dp[i]应该是多少呢,这个可以有很多解释,但基本都是直接奔着答案去解释的。

例如强行安慰自己爬到第0层,也有一种方法,什么都不做也就是一种方法即:dp[0] = 1,相当于直接站在楼顶。

但总有点牵强的成分。

那还这么理解呢:我就认为跑到第0层,方法就是0啊,一步只能走一个台阶或者两个台阶,然而楼层是0,直接站楼顶上了,就是不用方法,dp[0]就应该是0.

其实这么争论下去没有意义,大部分解释说dp[0]应该为1的理由其实是因为dp[0]=1的话在递推的过程中i从2开始遍历本题就能过,然后就往结果上靠去解释dp[0] = 1。

从dp数组定义的角度上来说,dp[0] = 0 也能说得通。

需要注意的是:题目中说了n是一个正整数,题目根本就没说n有为0的情况。

所以本题其实就不应该讨论dp[0]的初始化!

我相信dp[1] = 1,dp[2] = 2,这个初始化大家应该都没有争议的。

所以我的原则是:不考虑dp[0]如何初始化,只初始化dp[1] = 1,dp[2] = 2,然后从i = 3开始递推,这样才符合dp[i]的定义。

4.确定遍历顺序
从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,遍历顺序一定是从前向后遍历的

5.举例推导dp数组
举例当n为5的时候,dp table(dp数组)应该是这样的
在这里插入图片描述

困难:

抽象出动态公式,使用五步法去考虑。

题目名称:746. 使用最小花费爬楼梯

旧题目描述:

数组的每个下标作为一个阶梯,第 i 个阶梯对应着一个非负数的体力花费值 cost[i](下标从 0 开始)。

每当你爬上一个阶梯你都要花费对应的体力值,一旦支付了相应的体力值,你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时,你可以选择从下标为 0 或 1 的元素作为初始阶梯。

示例 1:

输入:cost = [10, 15, 20]
输出:15
解释:最低花费是从 cost[1] 开始,然后走两步即可到阶梯顶,一共花费 15 。
示例 2:

输入:cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出:6
解释:最低花费方式是从 cost[0] 开始,逐个经过那些 1 ,跳过 cost[3] ,一共花费 6 。
提示:

cost 的长度范围是 [2, 1000]。
cost[i] 将会是一个整型数据,范围为 [0, 999] 。

第一想法:

1.dp[i]是到达第i个阶梯的最少cost
2.dp[i]=dp[i-1]+cost[i-1]或者dp[i]=dp[i-2]+cost[i-2],选择最小的即可

解答思路:

修改之后的题意就比较明确了,题目中说 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯” 也就是相当于 跳到 下标 0 或者 下标 1 是不花费体力的, 从 下标 0 下标1 开始跳就要花费体力了。

1.确定dp数组以及下标的含义
使用动态规划,就要有一个数组来记录状态,本题只需要一个一维数组dp[i]就可以了。

dp[i]的定义:到达第i台阶所花费的最少体力为dp[i]。

对于dp数组的定义,大家一定要清晰!

2.确定递推公式
可以有两个途径得到dp[i],一个是dp[i-1] 一个是dp[i-2]。

dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。

dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢?

一定是选最小的,所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

3.dp数组如何初始化
看一下递归公式,dp[i]由dp[i - 1],dp[i - 2]推出,既然初始化所有的dp[i]是不可能的,那么只初始化dp[0]和dp[1]就够了,其他的最终都是dp[0]dp[1]推出。

那么 dp[0] 应该是多少呢? 根据dp数组的定义,到达第0台阶所花费的最小体力为dp[0],那么有同学可能想,那dp[0] 应该是 cost[0],例如 cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 的话,dp[0] 就是 cost[0] 应该是1。

这里就要说明本题力扣为什么改题意,而且修改题意之后 就清晰很多的原因了。

新题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 到达 第 0 个台阶是不花费的,但从 第0 个台阶 往上跳的话,需要花费 cost[0]。

所以初始化 dp[0] = 0,dp[1] = 0;

4.确定遍历顺序
最后一步,递归公式有了,初始化有了,如何遍历呢?

本题的遍历顺序其实比较简单,简单到很多同学都忽略了思考这一步直接就把代码写出来了。

因为是模拟台阶,而且dp[i]由dp[i-1]dp[i-2]推出,所以是从前到后遍历cost数组就可以了。

但是稍稍有点难度的动态规划,其遍历顺序并不容易确定下来。 例如:01背包,都知道两个for循环,一个for遍历物品嵌套一个for遍历背包容量,那么为什么不是一个for遍历背包容量嵌套一个for遍历物品呢? 以及在使用一维dp数组的时候遍历背包容量为什么要倒序呢?

这些都与遍历顺序息息相关。当然背包问题后续「代码随想录」都会重点讲解的!

5.举例推导dp数组
拿示例2:cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ,来模拟一下dp数组的状态变化
在这里插入图片描述

class Solution {public int minCostClimbingStairs(int[] cost) {int[] dp= new int[cost.length+1];dp[0]=0;dp[1]=0;for(int i=2;i<=cost.length;i++){dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[cost.length];}
}

收获:

注意dp[i]的边界定义问题,是否第一步不花费,cost大小与楼层的规定,dp[0]所代表的意义。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/417497.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

沐渥科技:两显氮气柜和三显氮气柜要怎么选择?

两显氮气柜通常指的是控制面板上有两个LED数码显示界面&#xff0c;用于显示温度和湿度&#xff1b;三显氮气柜则有三个LED数码显示界面&#xff0c;能够直观地显示出温度、湿度和含氧量。这样的设计便于用户快速全面地了解柜内环境状态&#xff0c;不需要额外的操作即可掌握所…

PHP智能匹配轻松预订自习室在线订座系统小程序源码

智能匹配&#xff0c;轻松预订——自习室在线订座系统 &#x1f4da;【开篇&#xff1a;告别排队&#xff0c;迎接智能学习新时代】&#x1f4da; 还在为找不到合适的自习室座位而烦恼吗&#xff1f;是不是每次去图书馆或自习室都要提前好久去排队占位&#xff1f;现在&#…

不同大模型代码解释对比

包含ChatGPT&#xff0c;讯飞星火&#xff0c;通义千问&#xff0c;腾讯元宝&#xff0c;智谱清言。 目标是想让大模型解释一个用于预处理人体骨骼关节三维坐标数据样本进行填补空帧的Python函数。 def f_padding_none(data):s data.copy()# print(pad the null frames with…

笔记整理—uboot番外(6)针对x210的网卡说明

对于x210而言&#xff0c;在三星中与九鼎官方的uboot都默认使用了二号串口。详见CONFIG_SERIALn&#xff08;n1~4&#xff09;。 更改串口后&#xff0c;应先插回原串口&#xff0c;进行iROM打印&#xff0c;内部iNnad校验核失败的信息&#xff0c;之后再插入其串口进行启动。 …

win10添加右键菜单打开VSCode

当进入一个文件夹后&#xff0c;想右键直接打开我的工程&#xff0c;用发现没有vscode项。本文就来介绍如何右键通过vsCode打开项目。步骤1&#xff1a;在桌面新建一个txt文档&#xff0c;用文本编辑器打开 步骤2&#xff1a; 查看vscode所在位置 在桌面找到vscode快捷键图标&…

EasyExcel 文件导出 - 合并某些列值相同的行

文章目录 EasyExcel 文件导出 - 合并某些列值相同的行最终效果实现思路创建单元格合并的策略类使用 EasyExcel 文件导出 - 合并某些列值相同的行 在数据处理与文件导出的过程中&#xff0c;我们常常会遇到各种特定的需求。今天&#xff0c;我们就来探讨一下使用 EasyExcel 进行…

【STM32+HAL库】---- 硬件IIC驱动0.96OLED

硬件开发板&#xff1a;STM32G0B1RET6 软件平台&#xff1a;cubemaxkeilVScode内容原著声明 代码借鉴学习于以下文章&#xff1a; STM32 使用硬件IIC驱动0.96寸4针IOLED显示器&#xff08;HAL库&#xff09; 1 新建cubemax工程 1.1 配置系统时钟RCC 1.2 配置引脚 1.3 导出工…

【盖世汽车-注册安全分析报告】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞…

SQLite3 数据库

一、SQLite3 命令 1. 基本命令 .tables&#xff1a;用于查看数据库中的表。.headers on/off&#xff1a;开启或者关闭表头&#xff0c;方便查看表结构。.mode column&#xff1a;使列对齐&#xff0c;增强数据的可读性。.width 列宽1 列宽2&#xff1a;设置每一列的列宽&…

抖音无水印视频下载

抖音想必大家都不陌生&#xff0c;大家经常会在抖音上刷到各种有意思的视频&#xff0c;但是我们想保存就会发现会有水印信息&#xff0c;那么我们要如何下载无水印的图片呢&#xff1f; 使用说明 我们可以先点击抖音的分享按钮&#xff0c;复制一下视频的链接 然后打开智游剪…

Spring6梳理5——基于XML管理Bean环境搭建

以上笔记来源&#xff1a; 尚硅谷Spring零基础入门到进阶&#xff0c;一套搞定spring6全套视频教程&#xff08;源码级讲解&#xff09;https://www.bilibili.com/video/BV1kR4y1b7Qc 目录 ①搭建模块 ②引入配置文件 ③创建BeanXML文件 ④创建Java类文件&#xff08;User…

pycharm项目里有中文右下角修改无效怎么办 包括注释里有中文

在我们编写pycharm项目时&#xff0c;可能会遇到项目里面有中文运行导致报错&#xff0c;即使我们在右下角修改编码格式&#xff0c;还是无效的 解决办法&#xff1a;点击左上角File,Settings,找到Editor里面的File Encodings ,圈住的位置都要改为UTF-8点击Apply就可以了

NAT技术-将多个内部网络设备映射到一个公共IP地址

问题&#xff1a; 今天上课的时候老师让我们在VMware填同一个子网ip 192.168.196.0&#xff0c;然后给我们的linux镜像都是同一个压缩包&#xff0c;结果我们的静态ip地址都是同一个。 192.168.196.0下面有256个ip地址&#xff0c;范围是192.168.196.0到192.168.196.255。我们…

浏览器百科:网页存储篇-Session storage应用实例(九)

1.引言 在前面的文章中&#xff0c;我们详细介绍了如何在 Chrome 浏览器中打开并使用 Session storage 窗格&#xff0c;进行数据的查看、编辑和管理。作为网页存储技术的重要组成部分&#xff0c;sessionStorage在提升用户体验和数据管理能力方面发挥了重要作用。在本篇《浏览…

谷歌seo网址如何快速被收录?

想让你的网站快速被搜索引擎收录&#xff0c;可以采取几种不同的策略。首先&#xff0c;确保你的网站内容丰富、有价值&#xff0c;搜索引擎更喜欢收录内容质量高的网站。同时&#xff0c;增强网站的外链建设&#xff0c;做好这些站内优化&#xff0c;接下来就是通过谷歌搜索控…

一款云笔记支持在线协同文档,脑图,白板演示的工具,多个设备同步,让灵感与你同行(附源码)

前言 在快节奏的工作环境中&#xff0c;如何高-效地记录、整理并分享工作笔记已经成为了一项重要的技能。传统的笔记方式往往难以满足跨设备、即时同步以及团队协作的需求&#xff0c;导致信息孤岛和工作效率低下。面对这样的挑战&#xff0c;我们迫切需要一种全新的工具来改变…

Type-C接口上的DisplayPort

随着高清视频和多媒体内容的快速发展&#xff0c;数字接口技术也在不断演进。在众多接口技术中&#xff0c;DisplayPort&#xff08;简称DP&#xff09;凭借其高带宽、高分辨率支持和多功能性&#xff0c;逐渐成为显示技术的领跑者。本文将深入探讨DisplayPort的技术特点、应用…

NineData云原生智能数据管理平台新功能发布|2024年8月版​​

本月发布 10 项更新&#xff0c;其中重点发布 5 项、其他发布 5 项。 重点发布​ 数据库 DevOps - 敏感数据保护功能大幅升级​ 敏感数据保护全新升级&#xff0c;新增支持敏感数据等级&#xff0c;方便进行分类分级管控&#xff0c;加入数据类型概念&#xff0c;用于智能识…

VMWARE VCENTER6.7 VCSA通过Web5480进行版本升级

VCENTER当前版本如下图 操作前先给VCENTER打一个快照&#xff0c;出问题可以立即回退 1、先下载VCSA镜像&#xff0c;并将VCSA镜像上传至DataStore中&#xff1b; 2、选中VCSA虚拟机&#xff0c;编辑配置 3、挂载新上传的VCSA镜像&#xff0c;一定要勾选“已连接”和“打开电源…

利用大模型实时提取和检索多模态数据探索-利用 Indexify 进行文档分析

概览 传统的文本提取方法常常无法理解非结构化内容&#xff0c;因此提取数据的数据往往是错误的。本文将探讨使用 Indexify&#xff0c;一个用于实时多模态数据提取的开源框架&#xff0c;来更好地分析pdf等非结构化文件。我将介绍如何设置 Indexify&#xff0c;包括服务器设置…