动态规划路径问题(不同路径 不同路径2 珠宝的最大价值 下降路径最小和 最小路径和)

本期题型:

1.    不同路径. - 力扣(LeetCode)

2.   不同路径2. - 力扣(LeetCode)

3.   珠宝的最大价值 . - 力扣(LeetCode)

4.   下降路径最小和. - 力扣(LeetCode)

5.   最小路径和  . - 力扣(LeetCode)

1.    不同路径

1.1 题目解析:

我们从此题中可以看出,机器人有向下和向右移动,并且只能走一步。 于是我们可以通过案例对此题进行分析

dp
00000000
11111111
01234567
013610152128

红色字体为我们机器人的位置,当我们开始填表时,就会发现当机器人走到(2,2)的位置时所走的步数为2 = (2,1)+(1,2)的位置,同理可得(2,3)的位置为 3 = (2,2)+(1,3)

我们从上面就能得出当我们想得到(m,n)的值时 就为 (m,n)= (m-1,n)+(m,n-1)的值。

2 算法原理:

1.2.1 状态表示:

    1.经验 + 题目要求

由上题的题目要求:我们可以看出我们要返回(m,n)的值,由此我们得出

dp[m][n]表示 :到达(m,n)位置的时候,一共走了多少种方式

1.2.2 状态转移方程:

最近的一步,划分问题

dp[i][j]

1.从[i-1,j]的位置走到[i,j]的位置

2.从[i,j-1]的位置走到[i,j]的位置

由此我们得出dp[i][j] = dp[i -1][j] +dp[i][j -1]

1.2.3 初始化:

00000000
11111111
01234567
0136101521

28

在我们定义二维数组时,总会有0下标为我们1的值,所以我们为了保证初始化的一致性,我们要先定义以下dp[0] 位置的值,因为我们都添加了一行一列,所以我要先初始化一下,但要注意一下问题

1.虚拟节点里面的值,保证后面填表的结果是正确的

2.下表的映射关系

1.2.4 填表顺序:

因为我们是要从上往下填写每一行 且每一行从左往右填写

1.2.5 返回值:

dp[m][n]

1.3 编写代码

我们编写代码分为4步:

1.创建dp表、

2.初始化、

3.填表.

4.填写返回值.

2.   不同路径2

2.1 题目分析

这题为不同路径的进阶版,我们可以看到题目中,机器人在遇到有障碍物时(并且障碍物的值被设为了1),由此我们可以对示例1分析得出:

初始
000
010
000

这个标红的位置就为障碍物,于是我们就可以遍历这个表,当遇到有1的值时我们不走,有0的值时我们就走,我们就能得出以下dp表

dp
111
1障碍物1
112

2 算法原理:

2.2.1 状态表示:

    1.经验 + 题目要求

这个题目要求是我们到达(m,n)位置的时候,一共走了多少种方式。

于是dp[m][n]就为到达(m,n)位置的时候,总共的方式。

2.2.2 状态转移方程:

最近的一步,划分问题

就是我们要怎么到达dp[i][j]的这个位置:

1.从[i-1,j]的位置走到[i,j]的位置

2.从[i,j-1]的位置走到[i,j]的位置

如果网格 (i,j) 上有障碍物,则 dp[i][j] 值为 0,表示走到该格子的方法数为 0;
否则网格 (i,j) 可以从网格 (i−1,j) 或者 网格 (i,j−1) 走过来,因此走到该格子的方法数为走到网格 (i−1,j) 和网格 (i,j−1) 的方法数之和,即 dp[i,j]=dp[i−1,j]+dp[i,j−1]。

2.2.3 初始化:

由于题目中,被标记为1的下表我们不能走,于是我们需要先遍历这个表,当遇到有1的值时我们不走,有0的值时我们就走。

同时为了保证初始化的一致性,我们要先定义以下dp[0] 位置的值,因为我们都添加了一行一列,所以我要先初始化一下,但要注意一下问题

1.虚拟节点里面的值,保证后面填表的结果是正确的

2.下表的映射关系

2.2.4 填表顺序:

因为我们是要从上往下填写每一行 且每一行从左往右填写

2.2.5 返回值:

dp[m][n]

2.3 编写代码

我们编写代码分为4步:

1.创建dp表、

2.初始化、

3.填表.

4.填写返回值.

3.   珠宝的最大价值

      3.1 题目分析

在本题当中我们可以看到我们只能从左上角开始拿珠宝,于是我们可以分析1得:

题目示例1
131
151
421

 我们每次只能向下和向右移动,并且只能走一步。因此我们每走一步要比较一下向左的值大还是向右的值大

3 算法原理:

3.2.1 状态表示:

    1.经验 + 题目要求

由上题的题目要求:我们从左上角走到右下角,可以拿到珠宝的最大价值

dp[m][n]表示 :到达(m,n)位置的时候,拿到珠宝的最大价值

3.2.2 状态转移方程:

最近的一步,划分问题

dp[ i ][ j ]

1.从[i-1,j]的位置走到[i,j]的位置后再走一步到我们的珠宝最大价值 - -> dp[i-1][j-1] + frame[i][j]

2.从[i,j-1]的位置走到[i,j]的位置后再走一步到我们的珠宝最大价值 - -> dp[i-1][j-1] + frame[i][j]

由此我们得出dp[i][j] = Math.max(dp[i -1][j] ,dp[i][j -1])+frame[i - 1][j - 1];

3.2.3 初始化:

我们要初始化自己所建的的这两行数字里面的值,因为我们要求的为最大值,所以说我们初始化数组不能初始比较大的值,不然会影响里面的数据。因此我们都设为零,因为数组里面默认的值就为零,所以说我们不用添加任何东西

1.虚拟节点里面的值,保证后面填表的结果是正确的

2.下表的映射关系

因为我们都定义了一行和一列,所以说我们下标映射的话不能为艾根接的指我们要减去一才是我们表格中这是对应的值。

3.2.4 填表顺序:

因为我们是要从上往下填写每一行 且每一行从左往右填写

3.2.5 返回值:

dp[m][n]

3.3 编写代码

4.   下降路径最小和

4.1 题目分析

我们可以看到题中,我们可以在第一行的任意位置选择进入,并且可以向下,向下左,和下右走

213
654
78

9

因为要求向下的最小值,所以第一行我们选1是最优解,之后我们在比较下三行的最小值并选择它,当我们走到最后一行时,此时里面存储了前两行最小值加每一行的值,所以此时我们的dp[i][j]中存储的值不唯一,我们还要便利最后一行的值,并找出最小的最即为我们返回的值。

4 算法原理:

4.2.1 状态表示:

    1.经验 + 题目要求

由上题的题目要求:从第一行中的任何元素开始,到最后一行的最小值

dp[m][n]表示 :到达(m,n)位置的时候,最小的路径和

4.2.2 状态转移方程:

最近的一步,划分问题

dp[ i ][ j ]

1.从[i-1,j-1]的位置走到[i,j]的位置后再走一步到我们的最小的路径和 - -> dp[i-1][j-1] + m[i][j]

2.从[i,j-1]的位置走到[i,j]的位置后再走一步到我们的最小的路径和 - -> dp[i ][j-1] + m[i][j]

3.从[i-1,j]的位置走到[i,j]的位置后再走一步到我们的最小的路径和 - -> dp[i-1][j ] + m[i][j]

由此我们得出dp[i][j] =Math.min(dp[i - 1][j - 1] Math.min(dp[i -1][j] ,dp[i][j -1]))+m[i ][j];

4.2.3 初始化:

123456
3214567
512359

看我们的状态转移方程可以从右上 上面 还有左上走过来,于是当我们走到最左边的时候就会发现它这个数组可能会越界。还有同你走到最上面或者是最右边的时候都会发生数据越界的情况,所以我们要先多加一行数据。因此我们要加两列和一行。此时咱们的dP表就不会发生数据越界的情况。

1.虚拟节点里面的值,保证后面填表的结果是正确的

为了保证咱们数据里面的值不会发生改变,所以我们在填表的时候,要把咱们第一行的值都改为零。此时我们就要思考一个问题,那左边和右边的值可以填0 嘛?当我们最左边和最右边填零的时候,我们就会发现他走的这个路径就会走到咱们这个零的位置。这是咱们初始化的位置,所以说咱们这两边不能设置为零。答案只能设置为最大值。这样设置的话不会影响咱们数组里面真实的值

2.下表的映射关系

因为咱们多加了两列和一行,所以说我们为了对照真实的值,我们那个m的下标映射就不能为 n 的值 和 m 的值

4.2.4 填表顺序:

因为我们是要从上往下填写每一行 且每一行从左往右填写

4.2.5 返回值:

我们要返回的最后一行的最小值

4.3 编写代码

5.   最小路径和 

5.1 题目分析

我们看到这一题有没有感觉很熟悉,没错就是上面的珠宝的最大价值,不过一个要最大值一个要最小最。

于是我们就不分析了,但要注意一点初始化

当我们不初始化时数组里面的值默认为0,因为要求最小值 ,因此我们要把我们初始多余的数组空设为最大值

代码编写:

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

ARM base instruction -- bfxil

Bitfield Extract and Insert Low copies a bitfield of <width> bits starting from bit position <lsb> in the source register to the least significant bits of the destination register, leaving the other destination bits unchanged. 位域提取并插入低位…

1.探索WebSocket:实时网络的心跳!

序言 你可能听说过"WebSokcet"这个词&#xff0c;感觉它好像很高深&#xff0c;但其实它是一个超级酷的小工具&#xff0c;让我们在Web应用里实现实时通信。想象一下&#xff0c;你可以像聊天一样&#xff0c;在浏览器和服务器之间来回“畅聊“&#xff0c;没有延迟…

springboot 修复 Spring Framework 特定条件下目录遍历漏洞(CVE-2024-38819)

刚解决Spring Framework 特定条件下目录遍历漏洞&#xff08;CVE-2024-38816&#xff09;没几天&#xff0c;又来一个新的&#xff0c;真是哭笑不得啊。 springboot 修复 Spring Framework 特定条件下目录遍历漏洞&#xff08;CVE-2024-38816&#xff09;https://blog.csdn.ne…

嵌入式硬件电子电路设计(二)开关电源BOOST升压电路

目录 升压电路原理 BOOST电路基本结构 BOOST电路工作过程分析 1. 开关导通阶段 2. 开关关断阶段 3. 稳定输出电压 BOOST电路工作的实际调研分析 1. 非同步BOOST电路 2. 同步BOOST电路 XL6009电路分析 SX1308电路分析 引言&#xff1a;前面已经讲述了Buck电路&#…

如何安装和使用PowerDesigner

教程目录 一、安装二、使用 一、安装 1、启动安装程序。 2、Trial&#xff0c;然后Next。 3、选PRC&#xff0c;同意协议&#xff0c;Next。 4、设置安装路径&#xff0c;Next。 5、Next。 6、全选&#xff0c;Next。 7、Next。 8、Next。 9、等待安装。 10、…

SQL进阶技巧:巧用异或运算解决经典换座位问题

目录 0 问题描述 1 数据准备 2 问题分析 2.1 什么是异或 2.2异或有什么特性? 2.3 异或应用 2.4 本问题采用异或SQL解决方案 3 小结 0 问题描述 表 seat中有2个字段id和student id 是该表的主键(唯一值)列,student表示学生姓名。 该表的每一行都表示学生的姓名和 ID。…

PAT甲级-1074 Reversing Linked List

题目 题目大意 给一个链表的头结点和总节点个数&#xff0c;以及k。每k个节点的链表都要翻转。 思路 链表可以用一个结构体数组来存储&#xff0c;先遍历一遍&#xff0c;过滤掉不在链表中的节点。然后将过滤好的节点放入res数组中&#xff0c;每k个元素用一次reverse()&…

PHP + Windows小皮面板 + VScode 安装教程

目录 1. 小皮面板安装包 下载 2、配置MySQL 可以在cmd命令框中使用 3. VScode安装 如有错误&#xff0c;烦请批评指正 1. 小皮面板安装包 下载 官方地址https://old.xp.cn/download.html 下载完后&#xff0c;一路next&#xff0c;文件路径自定义 2、配置MySQL 可以在cm…

ESP8266联网

目录 1.ESP8266连接热点 2.ESP8266创建热点 创建热点的ESP8266 连接热点的ESP8266 3.发送网络请求 案例一 案例二 4.连接服务器 接收信息开关灯 发布消息开关灯 5.ESP8266创建HTTP服务 ​编辑 ​编辑 ​编辑 6.ESP8266HTTP请求控制灯 ​编辑 7.ESP8266接收后端数据…

聊一聊Qt中的按钮

目录 QAbstractButton 功能概述 快捷键 默认按钮 按钮状态 自动重复功能 切换按钮 信号 子类化 API列表 QPushButton 按钮外观与功能 默认按钮 按钮的状态与模式 使用建议 菜单按钮 API QToolButton 创建工具按钮 用途示例 自动抬起功能 图标设置 外观与…

使用RabbitMQ实现微服务间的异步消息传递

使用RabbitMQ实现微服务间的异步消息传递 RabbitMQ简介 安装RabbitMQ 在Ubuntu上安装RabbitMQ 在CentOS上安装RabbitMQ 配置RabbitMQ 创建微服务 生产者服务 安装依赖 生产者代码 消费者服务 消费者代码 运行微服务 消息模式 直接模式 生产者代码 消费者代码 扇出模式 生产…

「实战应用」如何在 DHTMLX Scheduler 中实现动态主题切换?

创建响应式、直观的 UI 需要适应用户对应用程序各个方面的偏好。其中一项可显著提升用户体验的热门功能是能够在明暗主题之间切换。它在日程安排日历等综合组件中尤其有用。 本文将指导您在 DHTMLX Scheduler 中实现动态主题切换&#xff0c;使其适应用户设置的首选系统主题。…

Marin说PCB之电源的Surface Current Density知多少?

小编我是一位资深的国漫迷&#xff0c;像什么仙逆&#xff0c;斗破&#xff0c;斗罗&#xff0c;完美世界&#xff0c;遮天&#xff0c;凡人修仙传&#xff0c;少年歌行等&#xff0c;为了可以看这些视频小编我不惜花费了攒了很多年的私房钱去开了这个三个平台的会员啊&#xf…

【YApi】接口管理平台

一、简介 YApi 是一个用于前后端开发团队协作的 API 管理平台&#xff0c;帮助团队更加高效地进行 API 接口的设计、测试、文档管理和版本控制等工作。 YApi 主要功能&#xff1a; API 设计和管理&#xff1a;提供 API 设计和文档生成工具&#xff0c;使开发者能够轻松创建、…

【C/C++】字符/字符串函数(1)——由string.h提供

零.导言 什么是字符/字符串函数呢&#xff1f; 其实就是一类用于处理字符和字符串的函数。 而其中一部分函数包含在头文件 string.h 中&#xff0c;有 strlen strcpy strcat strcmp strncpy strncat strncmp strstr strtok strerror 等等 接下来我将逐个讲解这些函数。 一.str…

简单的kafkaredis学习之redis

简单的kafka&redis学习之redis 2. Redis 2.1 什么是Redis Redis是一种面向 “Key-Value” 数据类型的内存数据库&#xff0c;可以满足我们对海量数据的快速读写需求&#xff0c;Redis是一个 NoSQL 数据库&#xff0c;NoSQL的全称是not only sql&#xff0c;不仅仅是SQL&…

在 Visual Studio 中使用 Eigen 库

在 Visual Studio 中使用 Eigen 库 参考教程&#xff1a; 在 Visual Studio 中配置 Eigen库_vs调用eigen-CSDN博客 Eigen 是一个开源的 C 库&#xff0c;主要用来支持线性代数&#xff0c;矩阵和矢量运算&#xff0c;数值分析及其相关的算法。Eigen 除了需要 C 标准库以外&am…

认证鉴权框架之—sa-token

一、概述 Satoken 是一个 Java 实现的权限认证框架&#xff0c;它主要用于 Web 应用程序的权限控制。Satoken 提供了丰富的功能来简化权限管理的过程&#xff0c;使得开发者可以更加专注于业务逻辑的开发。 二、逻辑流程 1、登录认证 &#xff08;1&#xff09;、创建token …

MES(Manufacturing Execution System)制造执行系统解决方案 :高效协同, 实现数字化智能工厂

文章目录 引言I 常用功能模块车间实时数据设备维修证书管理II UI设计III 术语5M1Esee also引言 MES软件即制造企业生产过程执行管理软件,是一套面向制造企业车间执行层的生产信息化管理系统。 MES 可以为企业提供包括制造数据管理、计划排程管理、生产调度管理、库存管理、质…

Qt 实战(10)模型视图 | 10.5、代理

文章目录 一、代理1、简介2、自定义代理 前言&#xff1a; 在Qt的模型/视图&#xff08;Model/View&#xff09;框架中&#xff0c;代理&#xff08;Delegate&#xff09;是一个非常重要的概念。它充当了模型和视图之间的桥梁&#xff0c;负责数据的显示和编辑。代理可以自定义…