当前位置:   article > 正文

【LeetCode】 动态规划 刷题训练(三)_下降路径和 题目描述 给定一个 × n×n 的数字矩阵 a 定义矩阵中

下降路径和 题目描述 给定一个 × n×n 的数字矩阵 a 定义矩阵中

931. 下降路径最小和

点击查看:下降路径最小和


给你一个 n x n 的 方形 整数数组 matrix ,请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列(即位于正下方或者沿对角线向左或者向右的第一个元素)。具体来说,位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

输入:matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出:13
解释:如图所示,为和最小的两条下降路径

题目解析

当处于 (row,col)位置处时,下一行 可以选择 (row+1,col)位置 / (row+1,col-1)位置 /(row+1,col+1)位置处的元素

状态转移方程

dp[i][j]:表示从第一行位置开始到 [i,j]位置处的时候,最小的下降路径

根据最近的一步,划分问题


[i,j]位置可以由 [i-1,j-1]位置 / [i-1,j]位置 / [ i-1,j+1]位置 向下移动得到

所以可以分为三种情况:


第一种情况:
从 [i-1,j-1]位置 向下移动到到 [i,j] 位置
想要得到[i,j]位置的最小下降路径,就应该先得到[i-1,j-1]位置的最小下降路径 即 dp[i-1,j-1]
再加上[i,j]位置的路径 即 ob[i,j]
第一种情况下 [i,j]位置的最小下降路径为 : dp[i-1,j-1]+ob[i,j]


第二种情况:
从 [i-1,j]位置 向下移动到到 [i,j] 位置
想要得到[i,j]位置的最小下降路径,就应该先得到[i-1,j]位置的最小下降路径 即 dp[i-1,j]
再加上[i,j]位置的路径 即 ob[i,j]
第二种情况下 [i,j]位置的最小下降路径为 : dp[i-1,j]+ob[i,j]


第三种情况:
从 [i-1,j+1]位置 向下移动到到 [i,j] 位置
想要得到[i,j]位置的最小下降路径,就应该先得到[i-1,j+1]位置的最小下降路径 即 dp[i-1,j+1]
再加上[i,j]位置的路径 即 ob[i,j]
第三种情况下 [i,j]位置的最小下降路径为 : dp[i-1,j+1]+ob[i,j]


状态转移方程:
dp[i][j]= min( dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1] )+ob(i,j);

完整代码

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& ob) {
       
       int m=ob.size();
       int n=ob[0].size();
       //dp数组 扩列一行 两列
       //并将 m+1 个 vetcor 数组 的n+2个值 都初始化为正无穷大
       vector<vector<int>>dp(m+1,vector<int>(n+2,INT_MAX));
       //将dp 扩列的第一行初始化为0
      // dp[0].resize(n+2,0);
      int i=0;
       int j=0;
      for(j=0;j<n+2;j++)
      {
          dp[0][j]=0;
      }
       
       for(i=1;i<=m;i++)
       {
           //从[1,1]位置开始到[i,n]位置结束
           for(j=1;j<=n;j++)
           {
               //ob作为原数组,dp作为扩列数组
               //使用dp扩列的下标 寻找ob对应的原数组下标 行需减1 列减1
               dp[i][j]= min(min(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j+1])+ob[i-1][j-1];
           }
       }

     //寻找dp数组的最后一行的最小值
      int minsize=INT_MAX;
      for(j=1;j<=n;j++)
      {
         if(minsize>dp[m][j])
         {
             minsize=dp[m][j];
         }
      } 
     // 返回dp数组的最后一行的最小值
      return minsize;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

对于原数组来说,在蓝色区域处使用状态转移方程会发生越界问题,所以通过扩列的方法来解决这个问题


原数组的第一行,只能从当前位置到当前位置,所以储存原始数组元素的值
为了保护影响原数组的第一行的值,所以扩列后的数组第一行 都为0

剩余扩列的位置,若初始化为0,则干扰比较结果,所以为了不影响选取,将其 值 设置为正无穷大


如:6作为[i,j]位置 ,想要取得最小路径,则向下寻找,理应取到2位置处,
但是由于扩列后出现的0,就会选取0,从而导致结果错误

64. 最小路径和

点击查看:最小路径和


给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。

输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
输出:7
解释:因为路径 1→3→1→1→1 的总和最小。

题目解析

每次只能向下或者 向右走
从左上角 到右下角 的路径 中 寻找 最小路径和
图中最小路径为: 1+3+1+1+1=7


状态转移方程

dp[i][j] :表示 从起点位置(左上角)到 [i,j]位置 的时候, 此时的最小路径和

根据最近的一步,划分问题


想要到达[i,j]位置,只能从[i-1,j]位置向下走一步得到
或者 从[i,j-1]位置 向右走一步 得到

所以dp[i][j]划分为两种情况:


第一种从[i-1,j]位置向下得到[i,j]位置

想要得到[i,j]位置的最小路径 就先需要得到 [i-1,j]位置的最小路径 即dp[i-1,j]
再加上原数组ob 对应[i,j]位置的值 即ob[i,j]
第一种情况 下[i,j]位置的最小路径和为: dp[i-1,j]+ob[i,j]


第二种 从[i,j-1]位置 向右走一步 得到[i,j]位置

想要得到[i,j]位置的最小路径 就先需要得到 [i,j-1]位置的最小路径 即dp[i,j-1]
再加上原数组ob 对应[i,j]位置的值 即ob[i,j]
第二种情况 下[i,j]位置的最小路径和为: dp[i,j-1]+ob[i,j]


状态转移方程为:
dp[i][j] = min( dp[i-1][j],dp[i][j-1] )+ob[i,j];

完整代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& ob) {
          int m=ob.size();//行
          int n=ob[0].size();//列
          //将m+1个 vector数组 的n+1个值 设置为正无穷大
          //dp数组 将ob原数组 扩一行 和一列
          vector<vector<int>>dp(m+1,vector<int>(n+1,INT_MAX));
          int i=0;
          int j=0;
          //起点位置对应的上一个位置和左一个位置设置为0
          dp[0][1]=0;
          dp[1][0]=0;

          for(i=1;i<=m;i++)
          {
              for(j=1;j<=n;j++)
              {
                  //ob作为原数组 dp作为扩列数组
                  //通过扩列数组的下标 寻找原数组对应的下标 需行减1 列减1
                  dp[i][j]=min(dp[i-1][j],dp[i][j-1])+ob[i-1][j-1];
              }
          }
         // 由于dp是扩列数组 返回右下角 
          return dp[m][n];
          
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

初始化
若使用状态转移方程,则原数组的第一行和第一列都有可能出现越界问题,所以为了避免这个问题,将原数组扩一行和一列

在这里插入图片描述

因为此时并没有上一个位置或者左一个位置,所以dp 数组起点位置(start)的值应为 原数组内对应起点位置的值
为了不影响结果,将start对应的上一个位置和左一个位置都设置为0


红色区域 的上一个值若设置为0,则会进行状态转移方程时,会取到这个0,干扰结果,
所以为了不影响结果,将其设置为正无穷大


剩余的位置也同上述一个原因,会干扰结果,所以为了避免影响结果,都设置为正无穷大

174. 地下城游戏

点击查看:地下城游戏


恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。
有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增加健康点数)。
为了尽快解救公主,骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。

输入:dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出:7
解释:如果骑士遵循最佳路径:右 -> 右 -> 下 -> 下 ,则骑士的初始健康点数至少为 7 。

题目解析

从左上角 开始 到 右下角 结束
每次只能 向下或者 向右走

-2 -> -3 -> 3 -> 1 -> -5


第一房间时,就会损失2点健康点数,所以骑士想从第一个房间走出来 就需要3点健康点数,但是此时进入第二个房间,还要损失3点健康点数,骑士直接挂掉了 ,所以 初始3点健康点数不可以

将前两个房间走出来,就需要 骑士 起始健康点数为6点(健康点数为0就挂掉了),此时骑士健康点数为1点,
当走完第三个房间时 ,骑士加了3点健康点数,变为4点
当走完第四个房间时 ,骑士加了1点健康点数,变为5点
当走完走到最后一个房间时, 损失5点健康点数 ,骑士健康点数为0,直接挂掉了

所以骑士初始血量应为7点

状态转移方程

因为是通过初始血量判断的,而且不仅受到上面 还有后面的影响
所以要 以某一个位置 为起点 ,来解决问题

dp[i][j] 表示:以[i,j]位置出发,达到终点,存储的值为所需最低初始健康点数

根据最近的一步,划分问题


[i,j]位置,可以向下走一步达到[i+1,j]位置 或者 向右 走一步 达到 [i,j+1]位置

dp[i][j]分为两种情况:


第一种情况为 从[i,j]位置 向右移动到[i,j+1]位置

从[i,j]位置走出来 的健康点数 可以保证[i,j+1] 位置 走到终点
即 dp[i][j] +ob[i][j] >= dp[i][j+1]
dp[i][j]>= dp[i][j+1]-ob[i][j]
而dp[i][j]作为最低健康点数,所以 dp[i][j]=dp[i][j+1]-ob[i][j]


第 二 种情况为 从[i,j]位置 向下移动到[i+1,j]位置

从[i,j]位置走出来 的健康点数 可以保证[i+1,j] 位置 走到终点
dp[i][j] +ob[i][j] >= dp[i+1][j]
dp[i][j]>= dp[i+1][j]-ob[i][j]
而dp[i][j]作为最低健康点数,所以 dp[i][j]=dp[i+1][j]-ob[i][j]


状态转移方程为:
dp[i][j] = min(dp[i][j+1],dp[i+1][j])-ob[i][j];


若ob[i][j]过大,导致dp[i][j]的值为负数,就不符合要求,因为最低健康点数 为1

dp[i][j]=max(1,dp[i][j]);
若dp[i][j]为负数,就更换为1

完整代码

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& ob) {
      int m=ob.size();
      int n=ob[0].size();
      // 将 m+1个 vector 数组 的 n+1个值 都置为 正无穷大 
      vector<vector<int>>dp(m+1,vector<int>(n+1,INT_MAX));
     
    //从end位置走出来至少剩下1个健康点数
      dp[m-1][n]=1;
      dp[m][n-1]=1;
      int i=0;
      int j=0;
      for(i=m-1;i>=0;i--)
      {
          for(j=n-1;j>=0;j--)
          {
                dp[i][j]=min(dp[i][j+1],dp[i+1][j])-ob[i][j];
                //若dp[i][j]为负,将其置为1
                dp[i][j]=max(1,dp[i][j]);
          }
      }
      //dp[0][0]表示从起点位置开始,到终点至少需要多少初始健康点数
      return dp[0][0];
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

初始化
根据状态转移方程,最后一行和最右行 都会触发越界问题,所以将原数组进行 扩一行 和扩一列

从end位置才走出来后,一定至少剩下1点健康点数
可能向下走一步,或者向右走一步
从[i,j]位置走出来 的健康点数 可以保证[i,j+1] 位置 走到终点
所以两个位置 都设置为 1


当前红色区域位置,是需要比较它位置的下一个位置和右一个位置 取其中的小的那个位置,
但是下面的位置是虚拟的,所以不能算上,否则会干扰结果
所以其位置设置为 正无穷大


剩余的位置也同上述一个原因,会干扰结果,所以为了避免影响结果,都设置为正无穷大

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

闽ICP备14008679号