动态规划算法专题二--路径问题

目录

专题二： 路径问题

  题五 不同路径

1、算法解析

1、确定状态：

2、状态转移方程：

3、初始化：

4、填表顺序：

5、返回值：

2、代码

   题六 不同路径II

1、算法解析

1、确定状态：

2、状态转移方程：

3、初始化：

4、填表顺序：

5、返回值：

2、代码

    题七 礼物的最大价值

1、算法解析

1、确定状态：

2、状态转移方程：

3、初始化：

4、填表顺序：

5、返回值：

2、代码

     题八 下降路径最小和

1、算法解析

1、确定状态：

2、状态转移方程：

3、初始化：

4、填表顺序：

5、返回值：

2、代码

      题九 地下城游戏

1、算法解析

1、确定状态：

2、状态转移方程：

3、初始化：

4、填表顺序：

5、返回值：

2、代码

专题二： 路径问题

  题五 不同路径

91. 解码方法 - 力扣（LeetCode）62. 不同路径 - 力扣（LeetCode）91. 解码方法 - 力扣（LeetCode）​

1、算法解析

1、确定状态：

这里是一个二维数组，因此需要二维数组dp[i,j]
dp[i,j]的值，就是从起始位置，到达dp[I,j]位置的最多走法。

2、状态转移方程：

根据题目：
要走到dp[I,j]位置，要么是从左边dp[i-1]移动一格，要么是从上边dp[I,j-1]移动一格
因此，走到该位置，共有两种走法
即：左边或者上边
所以，dp[i,j] = dp[i-1,j] + dp[i,j-1]


3、初始化：

初始化解决的是填表越界的问题
现在我们的状态表是一个二维的数组，即dp[i,j]
每一个位置的dp值，等于dp[i,j] = dp[i-1,j] + dp[i,j-1]，即上边位置和左边位置的和
因此，第一行和第一列就需要初始化
这就是很麻烦
我们需要一个一个的进行手赋值，不好
有别的办法没有？
有的
就是多增加一个行和列（也叫虚拟位置），这样我们进行访问的时候，就不会越界
(这就是教科书上，关于背包问题的状态表，为什么会多一行和一列，就是这个初始化方法）
即：


但是这种方法，我们需要注意两个问题：
1、虚拟位置的初始化（一般情况是0，具体情况具体分析）
2、下标映射的问题

对于问题1，这个题目：
第一行的值，到达每一个位置的方法，只有一种，即从左往右，应该都为1
第一列的值，到达每一个位置的方法，也只有以一种，即从上往下，都为1
所以，初始化应该是这样的：

对于下表映射，体现在你写代码的时候，你需要自己把控。
这个你看着我写的代码自己体会。

4、填表顺序：

dp[i,j]位置的值，需要左边和上边的值
所以我们从上往下填表
每一行从左往右填表

5、返回值：

因为多加了一行一列
因此，返回 dp[m,n]

2、代码

class Solution {
public:int uniquePaths(int m, int n) {//1、常见dp表vector<vector<int>> dp(m+1,vector<int>(n+1));//2、初始化dp[1][0] =1;//3、填表for(int i = 1; i<=m; ++i)//行{for(int j = 1; j<=n; ++j)//列{dp[i][j] = dp[i-1][j] +dp[i][j-1];}}//4、返回值return dp[m][n];}
};

   题六 不同路径II

62. 不同路径 - 力扣（LeetCode）63. 不同路径 II - 力扣（LeetCode）62. 不同路径 - 力扣（LeetCode）​

1、算法解析

1、确定状态：

这里是一个二维数组，因此需要二维数组dp[i,j]
dp[i,j]的值，就是从起始位置，到达dp[I,j]位置的最多走法。

2、状态转移方程：

根据题目：
要走到dp[i,j]位置，要么是从左边dp[i-1]移动一格，要么是从上边dp[I,j-1]移动一格
因此，走到该位置，共有两种走法
即：左边或者上边
所以，dp[i,j] = dp[i-1,j] + dp[i,j-1]

这个题目，和上一题一模一样，只是多了一个限制条件，障碍物。仔细分析，障碍物不影响左边的值和上面的值，只是影响它的右边和下面的值。我们只需要对这两个位置进行特殊处理即可。如果dp[i][j]位置是障碍物，那么就直接为0，因为没有办法走到这个位置。同时，设置为0，就不会影响障碍物位置的右边和下边的值，因为加上障碍物位置的值也是0，相当于这个条路没有。


3、初始化：

初始化解决的是填表越界的问题
现在我们的状态表是一个二维的数组，即dp[i,j]
每一个位置的dp值，等于dp[i,j] = dp[i-1,j] + dp[i,j-1]，即上边位置和左边位置的和
因此，第一行和第一列就需要初始化
这就是很麻烦
我们需要一个一个的进行手赋值，不好
有别的办法没有？
有的
就是多增加一个行和列（也叫虚拟位置），这样我们进行访问的时候，就不会越界
(这就是教科书上，关于背包问题的状态表，为什么会多一行和一列，就是这个初始化方法）
即：


但是这种方法，我们需要注意两个问题：
1、虚拟位置的初始化（一般情况是0，具体情况具体分析）
2、下标映射的问题

对于问题1，这个题目：
第一行的值，到达每一个位置的方法，只有一种，即从左往右，应该都为1
第一列的值，到达每一个位置的方法，也只有以一种，即从上往下，都为1
所以，初始化应该是这样的：

对于下表映射，体现在你写代码的时候，你需要自己把控。
这个你看着我写的代码自己体会。

4、填表顺序：

dp[i,j]位置的值，需要左边和上边的值
所以我们从上往下填表
每一行从左往右填表

5、返回值：

因为多加了一行一列
因此，返回 dp[m,n]

2、代码

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {//1、创建dp表int m = obstacleGrid.size(), n=obstacleGrid[0].size();vector<vector<int>> dp(m+1, vector<int>(n+1));//2、初始化dp[1][0] =1;//3、填表for(int i = 1; i<=m; ++i){for(int j = 1; j<=n; ++j){//判断该位置是否是障碍，是，则直接跳过if(obstacleGrid[i-1][j-1] == 1)dp[i][j] = 0;elsedp[i][j] = dp[i-1][j] + dp[i][j-1];}}//4、返回值return dp[m][n];}
};

    题七 礼物的最大价值

63. 不同路径 II - 力扣（LeetCode）LCR 166. 珠宝的最高价值 - 力扣（LeetCode）63. 不同路径 II - 力扣（LeetCode）​

1、算法解析

1、确定状态：

这里是一个二维数组，因此需要二维数组dp[i,j]
dp[i,j]的值，就是从起始位置，到达dp[I,j]位置的最大珠宝价值

2、状态转移方程：

根据题目：
要走到dp[I,j]位置，要么是从左边dp[i-1]移动一格，要么是从上边dp[I,j-1]移动一格
因此，走到该位置，共有两种走法
即：左边或者上边
但是，注意是最大价值
所以，dp[i,j] = max(dp[i-1,j] ，dp[i,j-1]) + g[i-1][j-1]

3、初始化：

初始化解决的是填表越界的问题
现在我们的状态表是一个二维的数组，即dp[i,j]
根据状态转移表，每一个位置的dp值，dp[i,j] = max(dp[i-1,j] ，dp[i,j-1]) + g[i-1][j-1]，即上边位置和左边位置的最大值
因此，第一行和第一列就需要初始化
这就是很麻烦
我们需要一个一个的进行手赋值，不好
有别的办法没有？
有的
就是多增加一个行和列（也叫虚拟位置），这样我们进行访问的时候，就不会越界
但是这种方法，我们需要注意两个问题：
1、虚拟位置的初始化（一般情况是0，具体情况具体分析）
2、下标映射的问题

对于问题1，这个题目：
第一行第一列都是0

对于下表映射，体现在你写代码的时候，你需要自己把控。
这个你看着我写的代码自己体会。

4、填表顺序：

dp[i,j]位置的值，需要左边和上边的值
所以我们从上往下填表
每一行从左往右填表

5、返回值：

因为多加了一行一列
因此，返回 dp[m,n]

2、代码

class Solution {
public:int jewelleryValue(vector<vector<int>>& frame) {//1、创建dp表int m = frame.size(), n = frame[0].size();vector<vector<int>> dp(m+1, vector<int> (n+1));//2、初始化//第一行第一列都是0，vector<int>初始化默认值为0，所以不用处理//3、填表for(int i = 1; i<=m; ++i){for(int j = 1; j<=n; ++j){dp[i][j] += max(dp[i-1][j],dp[i][j-1]) + frame[i-1][j-1];}}//4、返回值return dp[m][n];}
};

     题八 下降路径最小和

931. 下降路径最小和 - 力扣（LeetCode）​

1、算法解析

1、确定状态：

这里是一个二维数组，因此需要二维数组dp[i,j]
dp[i,j]的值，就是该位置的下降最小路径

2、状态转移方程：

根据题目：
要走到dp[I,j]位置，是从上一行的三个位置到达，如图的A，B，C位置


因此，走到该位置，共有三种走法
但是，注意是最小价值
所以，dp[i,j] = max(A，B，C) + m[i-1][j-1]

3、初始化：

初始化解决的是填表越界的问题
现在我们的状态表是一个二维的数组，即dp[i,j]
根据状态转移表，每一个位置的dp值，dp[i,j] = max(A，B，C) + m[i-1][j-1]，
我们按照老办法，多搞一行和一列
就是多增加一个行和列（也叫虚拟位置）。但是，这题有一点特殊，需要多加两列：一看图你就懂了

这样我们进行访问的时候，就不会越界
但是这种方法，我们需要注意两个问题：
1、虚拟位置的初始化（一般情况是0，具体情况具体分析）
2、下标映射的问题

对于问题1，这个题目：画图

对于下表映射，体现在你写代码的时候，你需要自己把控。
这个你看着我写的代码自己体会。

4、填表顺序：

dp[i,j]位置的值，需要上一行三个位置的值
所以我们从上往下填表

5、返回值：

需要返回最后一行的最小值

2、代码

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {//1、创建dp表int n = matrix.size();vector<vector<int>> dp(n+1, vector<int> (n+2));//2、初始化for(int i = 1; i<=n; ++i){dp[i][0] = dp[i][n+1] = INT_MAX;}//3、填表for(int i = 1; i<=n; ++i){for(int j = 1; j<=n; ++j){dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i-1][j+1])) + matrix[i-1][j-1];}}//4、返回值int ret = INT_MAX;for(int i = 1; i<= n; ++i){ret = min(dp[n][i],ret);}return ret;}
};

      题九 地下城游戏

174. 地下城游戏 - 力扣（LeetCode）​

1、算法解析

1、确定状态：

这里是一个二维数组，因此需要二维数组dp[i,j]
dp[i,j]的值，就是从dp[i][j]位置，到达终点位置时，骑士最少的生命值

2、状态转移方程：

根据题目：
这一题，我们使用从前往后的策略。

3、初始化：

初始化解决的是填表越界的问题
现在我们的状态表是一个二维的数组，即dp[i,j]
根据状态转移表，每一个位置的dp值，dp[i,j] = min(dp[i-1,j] ，dp[i,j-1]) - d[i][j]
因此，最后一行和最后一列就需要初始化
这样我们进行访问的时候，就不会越界
此时，我们需要注意：
1、虚拟位置的初始化（一般情况是0，具体情况具体分析）
2、下标映射的问题

对于问题1，这个题目：
画图：根据状态转移方程，我们的dp值需要右边和左边的值，所以最后一行和最后一列会越界。我们多开一行和一列。初始化的时候，只需要在我画圈的地方置1，其余位置置正无穷即可。为什么？因为原二维数组的最后一个位置是公主的位置，当骑士走到这里，血量至少要为1，所以从两个位置都设置为1，事实上，这两个位置只要有一个位置为1即可。

至于下标映射，体现在你写代码的时候，你需要自己把控。
这个你看着我写的代码自己体会。

4、填表顺序：

dp[i,j]位置的值，需要右边和下边的值
所以我们从下往上填表
每一行从右填往左填表

5、返回值：

返回 dp[0,0]

2、代码

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {//1、创建dp表int m = dungeon.size(), n = dungeon[0].size();vector<vector<int>> dp(m+1, vector<int> (n+1, INT_MAX));if(m == 0) return 1;//2、初始化dp[m][n-1] = 1;//3、填表for(int i = m-1; i>=0; --i){for(int j = n-1; j>=0; --j){dp[i][j] = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j];dp[i][j] = max(1, dp[i][j]);}                }//4、返回值return dp[0][0];} 
};

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

前端面试题(CSS篇六)

前端面试题(CSS篇六)

一、浏览器如何判断是否支持 webp 格式图片 &#xff08;1&#xff09;宽高判断法。通过创建image对象&#xff0c;将其src属性设置为webp格式的图片&#xff0c;然后在onload事件中获取图片的宽高&#xff0c;如果能够获取&#xff0c;则说明浏览器支持webp格式图片。如果不能…
阅读更多...
Qt：13.多元素控件(QLinstWidget-用于显示项目列表的窗口部件、QTableWidget- 用于显示二维数据表)

Qt：13.多元素控件(QLinstWidget-用于显示项目列表的窗口部件、QTableWidget- 用于显示二维数据表)

目录 一、QLinstWidget-用于显示项目列表的窗口部件&#xff1a; 1.1QLinstWidget介绍&#xff1a; 1.2属性介绍&#xff1a; 1.3常用方法介绍&#xff1a; 1.4信号介绍&#xff1a; 1.5实例演示&#xff1a; 二、QTableWidget- 用于显示二维数据表&#xff1a; 2.1QTabl…
阅读更多...
Vue学习笔记（小满zs）

Vue学习笔记（小满zs）

本文章记录一下我的学习笔记&#xff0c;供复习参考。&#x1f3c6; 向大佬学习&#xff01;&#xff01;&#xff01; ⭐小满zs Nodejs Nodejs 三层组成 libuv&#xff08;处理事件循环、I/O操作&#xff09; 第三方库&#xff08;处理HTTP等&#xff09; V8引擎&#xff08…
阅读更多...
Windows10系统下mysql5.6的安装步骤

Windows10系统下mysql5.6的安装步骤

1.下载mysql 下载地址&#xff1a;https://downloads.mysql.com/archives/community/ 在这里我们下载zip的包 2.解压mysql包到指定目录 3. 添加my.ini文件 # For advice on how to change settings please see # http://dev.mysql.com/doc/refman/5.6/en/server-configurat…
阅读更多...
【欧美高端NFT链游--大嘴怪/小黄人】链游

【欧美高端NFT链游--大嘴怪/小黄人】链游

#游戏#链游 呆萌的小黄人出现在大嘴怪的地盘上会发生什么有趣的事情呢?#动画#游戏#小黄人 大嘴怪与小黑人之间起了冲突&#xff0c;大嘴怪爆发了&#xff0c;他决定要给小黑人们一点颜色瞧瞧&#xff0c;用自己的拳头&#xff0c;以及&#xff1f;?嘴巴&#xff01;大嘴怪有…
阅读更多...
视频号的视频，一键就下载了，方法全在这儿了！

视频号的视频，一键就下载了，方法全在这儿了！

居然还有人不知道&#xff1a;视频号里面的视频是没有地址的&#xff0c;只能有微信自带的浏览器中打开。 所以很多人在视频号找到想要的素材&#xff0c;却无法下载&#xff0c;表示很苦恼。 几天每天都有人群里求助&#xff1a;“求好心人帮我下载一下这个视频&#xff01;…
阅读更多...
漏洞挖掘 | 记某证书站任意账号接管漏洞

漏洞挖掘 | 记某证书站任意账号接管漏洞

下文中所述漏洞已修复 在前段时间的漏洞挖掘中&#xff0c;上了某证书站&#xff0c;打点的一处逻辑漏洞 访问某一站点&#xff0c;发现了一处登录页 点击登录按钮之后&#xff0c;发现该站点大概率是自写站点&#xff0c;存在逻辑漏洞的可能性大大增大&#xff0c;利用前期信…
阅读更多...
产品软文应该怎么写，纯干货

产品软文应该怎么写，纯干货

产品软文是把一款产品的卖点很含蓄地表达在文章里面&#xff0c;通过特定的方式让这些枯燥的说明变得亲近人&#xff0c;以此传达一种价值观念&#xff0c;从而让人们对它产生一定的认知&#xff0c;能够潜移默化的感染着客户&#xff0c;可以提高产品和品牌的可见性和知名度。…
阅读更多...
typora 两边太宽，设置宽度

typora 两边太宽，设置宽度

步骤&#xff1a; 查看目前使用主题类型 文件 —> 偏好设置 —> 外观 —> 打开主题文件夹 修改对应的主题&#xff1a;max-width
阅读更多...
ubuntu笔记本X86安装nomachine客户端

ubuntu笔记本X86安装nomachine客户端

资源下载： 链接: link 一、首先下载文件 nomachine_8.2.3_4_x86_64.tar.gz到桌面。 二、打开终端，依次输入 进入root模式，需要输入密码，密码不可见。 sudu su复制nomachine_8.2.3_4_x86_64.tar.gz粘贴到/usr目录: cp -r nomachine_8.2.3_4_x86_64.tar.gz /usr进入
阅读更多...
【后端开发实习】用MongoDB实现仓库管理的出库入库实战

【后端开发实习】用MongoDB实现仓库管理的出库入库实战

用MongoDB实现仓库管理的出库入库 MongoDB什么是MongoDBMongoDB安装以及开始运行配置启动以及mongoshmongodb的基础使用命令启动和使用MongoDB服务数据库操作集合操作文档操作 项目部署在数据库中创建一张商品信息表提供信息表的增删改查操作接口 MongoDB 什么是MongoDB Mong…
阅读更多...
‘wget‘ 不是内部或外部命令,也不是可运行的程序

‘wget‘ 不是内部或外部命令,也不是可运行的程序

在Windows环境下创建了虚拟环境并安装了wget包&#xff0c;但在使用该命令的时候仍然报错&#xff0c;‘wget’ 不是内部或外部命令,也不是可运行的程序 解决方案&#xff1a; 去官网下载对应位数的.exe文件&#xff0c;将其放在C:\Windows\System32目录下即可, 别下错版本&a…
阅读更多...
C语言-预处理详解

C语言-预处理详解

文章目录 &#x1f3af;引言&#x1f453;预处理详解1.预定义符号1.1 __FILE__1.2 __LINE__1.3 __DATE__1.4 __TIME__1.5 __STDC__ 2.#define定义常量2.1 定义数值常量2.2 定义字符串常量 3.#define中使用参数3.1**使用示例**3.2注意事项 4.宏替换的规则5.宏函数和函数的对比5.…
阅读更多...
windows远程连接virtualbox的ubuntu问题

windows远程连接virtualbox的ubuntu问题

一.安装vritualbox ubuntu&#xff0c;18、22版本比较稳定 1.推荐使用ubuntu22版本 2.ubuntu24对内存要求较高至少4G&#xff0c;时不时会死机&#xff0c;安装老是崩溃&#xff0c;恢复不了&#xff0c;如果电脑性能强悍那可以尝试。 3.ubuntu18 对vscode最高只能支持1.85.…
阅读更多...
Spring中的工厂模式详解及应用示例

Spring中的工厂模式详解及应用示例

1. Spring中的BeanFactory BeanFactory是一个接口&#xff0c;表示它是一个工厂&#xff0c;负责生产和管理bean。在Spring中&#xff0c;BeanFactory是IOC容器的核心接口&#xff0c;定义了管理Bean的通用方法&#xff0c;如 getBean 和 containsBean。 BeanFactory与IOC容器…
阅读更多...
海外视频媒体发布/发稿：如何在国外媒体以视频的形式宣发

海外视频媒体发布/发稿：如何在国外媒体以视频的形式宣发

1. 背景介绍 在如今数字化时代&#xff0c;每个国家都拥有着各自的视频媒体平台&#xff0c;而主流媒体也都纷纷加入了视频发布的行列。视频媒体的宣发形式主要包括油管Youtube等视频分享平台&#xff0c;以及图文配合的发布方式。通过在视频中夹带链接&#xff0c;媒体可以以…
阅读更多...
C++ 宏和内联、范围for、nullptr

C++ 宏和内联、范围for、nullptr

C 宏函数和内联函数、范围for、nullptr 宏函数和内联函数 ​ 函数重载中提到过&#xff0c;一个程序编译需要经过四个阶段&#xff0c;第一个阶段预处理中有一个操作是宏替换。由于是替换&#xff0c;所以宏不建立栈帧&#xff0c;且没有数据类型的限制&#xff0c;能够提高我…
阅读更多...
CCSI: 数据无关类别增量学习的持续类特定印象| 文献速递-基于深度学习的多模态数据分析与生存分析

CCSI: 数据无关类别增量学习的持续类特定印象| 文献速递-基于深度学习的多模态数据分析与生存分析

Title 题目 CCSI: Continual Class-Specific Impression for data-free class incremental learning CCSI: 数据无关类别增量学习的持续类特定印象 01 文献速递介绍 当前用于医学影像分类任务的深度学习模型表现出令人鼓舞的性能。这些模型大多数需要在训练之前收集所有的…
阅读更多...
element plus 实现跨页面+跨tab栏多选

element plus 实现跨页面+跨tab栏多选

文章目录 element plus 层面数据层面 菜鸟好久没写博客了&#xff0c;主要是没遇见什么很难的问题&#xff0c;今天碰见了一个没有思路的问题&#xff0c;解决后立马来和大家伙分享了&#xff01; 菜鸟今天要实现一个需求&#xff0c;就是&#xff1a;实现跨页面跨 tab栏 多选…
阅读更多...
解锁算力新极限，Xilinx UltraScale+赋能的高性能低延时FPGA加速卡

解锁算力新极限，Xilinx UltraScale+赋能的高性能低延时FPGA加速卡

01、产品概述 AiHPC-V9P 是一款基于 AMD Virtex UltraScale FPGA VU9P 的 PCIe Gen3.0 x16 接口智能网卡&#xff0c;具有最大2*200GbE /或者16*10GbE(典型应用&#xff09;接入容量的高性能低延时智能网卡。 对外接口支持两组QSFP-DD 最高25Gb/s x8Lane 光口接入&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023