【LeetCode】 动态规划 刷题训练(三)_下降路径和 题目描述 给定一个 × 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

---

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

---

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