状态转移：简单分析一下

示例 2：
输入：dungeon = [[0]]
输出：1

提示：

• m == dungeon.length
• n == dungeon[i].length
• 1 <= m, n <= 200
• 1000 <= dungeon[i][j] <= 1000

思路：

1. 状态表示：这道题如果我们定义成：从起点开始，到达 [i, j] 位置的时候，所需的最低初始健康点数。处理这种情况仅需让 dp[i][j] 与 1 取一个最大值即可：dp[i][j] = max(1, dp[i][j])

   3. 初始化：可以在最前面加上一个「辅助结点」，帮助我们初始化。
      由于到 [i, j] 位置两种情况，并且我们要找的是最小路径，因此只需要这两种情况下的最小值，再加上 [i, j] 位置上本身的值即可。

      1. 状态表示：dp[i][j] 表示：走到 [i, j] 位置处，一共有多少种方式。
         这个时候我们要换一种状态表示：从 [i, j] 位置出发，到达终点时所需要的最低初始健康点数。地下城是由 m x n 个房间组成的二维网格。综上所述，定义状态表示为：dp[i][j] 表示：从 [i, j] 位置出发，到达终点时所需的最低初始健康点数。通过移项可得： x >= dp[i + 1][j] - dungeon[i][j] 。
         于是 dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i - 1][j + 1])) + matrix[i][j] 。

      代码如下：

      class Solution {		public:		    int minFallingPathSum(vector<vector<int>>& matrix)		    {		        int len = matrix.size();				        // 多开一行，两列，因为dp[i][j]的值需要用到dp[i - 1][j], dp[i - 1][j - 1], dp[i - 1][j + 1]		        vector<vector<int>> dp(len + 1, vector<int>(len + 2, INT_MAX));				        // 初始化，为了后面填表的正确性		        for (int i = 0; i <= len; i++) dp[0][i] = 0;				        // dp[i][j] 表示：到达 [i, j] 位置时，所有下降路径中的最小和		        for (int i = 1; i <= len; i++)		        {		            for (int j = 1; j <= len; j++)		            {		                dp[i][j] = min(min(dp[i - 1][j], dp[i - 1][j - 1]), dp[i - 1][j + 1]) + matrix[i - 1][j - 1];		            }		        }				        // 返回最后一行的最小值		        int ret = INT_MAX;		        for (int j = 0; j <= len; j++) ret = min(ret, dp[len][j]);		        return ret;		    }		};

      5. 最小路径和

      题目链接-> Leetcode -64.最小路径和

      Leetcode -64.最小路径和

      题目：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
      从左上角到右下角一共有 2 条不同的路径：

      1. 向右->向右->向下->向下
      2. 向下->向下->向右->向右

      示例 2：
      输入：obstacleGrid = [[0, 1], [0, 0]]
      输出：1

      提示：

      • m == obstacleGrid.length
      • n == obstacleGrid[i].length
      • 1 <= m, n <= 100
      • obstacleGrid[i][j] 为 0 或 1

      思路：本题为不同路径的变型，只不过有些地方有「障碍物」，只要在「状态转移」上稍加修改就可解决。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

      骑士的初始健康点数为一个正整数。

   4. 返回值：根据状态表示，我们要返回的结果是 dp[m][n].

   代码如下：

   class Solution {		public:		    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)		    {		        int m = obstacleGrid.size(), n = obstacleGrid[0].size();				        // 多开一行一列方便初始化		        vector<vector<int>> dp(m + 1, vector<int>(n + 1));		        dp[0][1] = 1; // 为了后面填表的正确				        // dp[i][j] 表示：⾛到 [i, j] 位置处，⼀共有多少种方式		        for (int i = 1; i <= m; i++)		        {		            for (int j = 1; j <= n; j++)		            {		                // 原矩阵中的位置不是障碍物		                if (obstacleGrid[i - 1][j - 1] != 1)		                {		                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];		                }		            }		        }		        return dp[m][n];		    }		};

   3. 珠宝的最高价值

   题目链接-> Leetcode -LCR 166.珠宝的最高价值

   Leetcode -LCR 166.珠宝的最高价值

   题目：现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。那么从左上角到右下角将会有多少条不同的路径？
   网格中的障碍物和空位置分别用 1 和 0 来表示。因为我们要的是最小
   值，因此这种情况下的 x = dp[i][j + 1] - dungeon[i][j] ；
   ii. 走到下边，然后走向终点；那么我们在 [i, j] 位置的最低健康点数加上这⼀个位置的消耗，应该要大于等于下边位置的最低健康点数，也就是： x + dungeon[i][j] >= dp[i + 1][j] 。

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

   示例 2：
   输入：matrix = [[-19, 57], [-40, -5]]
   输出： - 59
   解释：如图所示，为和最小的下降路径

   

   提示：

   • n == matrix.length == matrix[i].length
   • 1 <= n <= 100
   • 100 <= matrix[i][j] <= 100

   思路：

   1. 状态表示：dp[i][j] 表示：到达 [i, j] 位置时，所有下降路径中的最小和。
   2. 返回值：注意这里不是返回 dp[m][n] 的值；题目要求「只要到达最后一行」就行了，因此这里应该返回「 dp 表中最后一行的最小值」。

   代码如下：

   class Solution {		public:		    int calculateMinimumHP(vector<vector<int>>& dungeon)		    {		        int m = dungeon.size(), n = dungeon[0].size();		        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));		        dp[m][n - 1] = 1;				        // 从右下角往回推		        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];				                // 如果减到负数，说明这里的血包很大，即使是负数到这里都可以，但是这是不符合常理的		                // 所以需要将这里置成 1 即可		                if (dp[i][j] <= 0) dp[i][j] = 1;    		            }		        }				        // 返回最初位置		        return dp[0][0];		    }		};