【LeetCode】动态规划刷题训练(三)-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode】动态规划刷题训练(三)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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;
    }
};

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

原数组的第一行，只能从当前位置到当前位置，所以储存原始数组元素的值
为了保护影响原数组的第一行的值，所以扩列后的数组第一行都为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];
          
    }
};

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

【LeetCode】动态规划刷题训练(三)

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

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

剩余的位置也同上述一个原因，会干扰结果，所以为了避免影响结果，都设置为正无穷大文章来源地址https://www.toymoban.com/news/detail-498981.html

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];
    }
};