devbox
木道寻08
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

动态规划算法专题二--路径问题_动态解区间算法规划路径

作者：木道寻08 | 2024-08-07 05:55:43

赞

踩

动态解区间算法规划路径

目录

专题二： 路径问题

  题五 不同路径

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、代码

  1. class Solution {
  2. public:
  3.     int uniquePaths(int m, int n) {
  4.         //1、常见dp表
  5.         vector<vector<int>> dp(m+1,vector<int>(n+1));
  6.         
  7.         //2、初始化
  8.         dp[1][0] =1;
  9.         
  10.         //3、填表
  11.         for(int i = 1; i<=m; ++i)//行
  12.         {
  13.             for(int j = 1; j<=n; ++j)//列
  14.             {
  15.                 dp[i][j] = dp[i-1][j] +dp[i][j-1];
  16.             }
  17.         }
  18.  
  19.         //4、返回值
  20.         return dp[m][n];
  21.  
  22.     }
  23. };

   题六 不同路径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、代码

  1. class Solution {
  2. public:
  3.     int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
  4.         //1、创建dp表
  5.         int m = obstacleGrid.size(), n=obstacleGrid[0].size();
  6.         vector<vector<int>> dp(m+1, vector<int>(n+1));
  7.  
  8.         //2、初始化
  9.         dp[1][0] =1;
  10.  
  11.         //3、填表
  12.             for(int i = 1; i<=m; ++i)
  13.             {
  14.                 for(int j = 1; j<=n; ++j)
  15.                 {
  16.                     //判断该位置是否是障碍，是，则直接跳过
  17.                     if(obstacleGrid[i-1][j-1] == 1)
  18.                         dp[i][j] = 0;
  19.                     else
  20.                         dp[i][j] = dp[i-1][j] + dp[i][j-1];
  21.  
  22.                 }
  23.             }
  24.  
  25.         //4、返回值
  26.         return dp[m][n];
  27.     }
  28. };

    题七 礼物的最大价值

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、代码

  1. class Solution {
  2. public:
  3.     int jewelleryValue(vector<vector<int>>& frame) {
  4.         //1、创建dp表
  5.         int m = frame.size(), n = frame[0].size();
  6.         vector<vector<int>> dp(m+1, vector<int> (n+1));
  7.         
  8.         //2、初始化
  9.         //第一行第一列都是0，vector<int>初始化默认值为0，所以不用处理
  10.  
  11.         //3、填表
  12.         for(int i = 1; i<=m; ++i)
  13.         {
  14.             for(int j = 1; j<=n; ++j)
  15.             {
  16.                 dp[i][j] += max(dp[i-1][j],dp[i][j-1]) + frame[i-1][j-1];
  17.             }
  18.         }
  19.  
  20.         //4、返回值
  21.         return dp[m][n];
  22.     }
  23. };

     题八 下降路径最小和

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、代码

  1. class Solution {
  2. public:
  3.     int minFallingPathSum(vector<vector<int>>& matrix) {
  4.         //1、创建dp表
  5.         int n = matrix.size();
  6.         vector<vector<int>> dp(n+1, vector<int> (n+2));
  7.  
  8.         //2、初始化
  9.         for(int i = 1; i<=n; ++i)
  10.         {
  11.             dp[i][0] = dp[i][n+1] = INT_MAX;
  12.         }
  13.         
  14.         //3、填表
  15.         for(int i = 1; i<=n; ++i)
  16.         {
  17.             for(int j = 1; j<=n; ++j)
  18.             {
  19.                 dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i-1][j+1])) + matrix[i-1][j-1];
  20.             }
  21.         }
  22.  
  23.         //4、返回值
  24.         int ret = INT_MAX;
  25.         for(int i = 1; i<= n; ++i)
  26.         {
  27.             ret = min(dp[n][i],ret);
  28.         }
  29.         return ret;
  30.     }
  31. };

      题九 地下城游戏

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、代码

  1. class Solution {
  2. public:
  3.     int calculateMinimumHP(vector<vector<int>>& dungeon) {
  4.         //1、创建dp表
  5.         int m = dungeon.size(), n = dungeon[0].size();
  6.         vector<vector<int>> dp(m+1, vector<int> (n+1, INT_MAX));
  7.         if(m == 0) return 1;
  8.         
  9.         //2、初始化
  10.         dp[m][n-1] = 1;
  11.  
  12.         //3、填表
  13.         for(int i = m-1; i>=0; --i)
  14.         {
  15.             for(int j = n-1; j>=0; --j)
  16.             {
  17.                 dp[i][j] = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j];
  18.                 dp[i][j] = max(1, dp[i][j]);
  19.             }                
  20.         }
  21.  
  22.         //4、返回值
  23.         return dp[0][0];
  24.     } 
  25. };

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/木道寻08/article/detail/941199
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号