【LeetCode 动态规划】路径问题：LC

文章目录

• • • 1. 最小路径和🆗
    • 2. 地下城游戏🆗

      1. 最小路径和🆗

      题目链接🔗

      ---

      • 🐧解题思路： 动态规划~路径问题

        🍎① 状态表示：

        dp[i][j] ：表示以 (i, j) 位置为终点，从起点到 (i，j)位置的最小值。

        🍎② 初始化：

        我们求的是最小值，所以初始化的时候，应该把dp初始化为INT_MAX，但是有两个特殊的点要初始化为0，dp[0][1] = 0, dp[1][0] = 0; 因为dp[1][1]作为起始位置，它的值要等于grid[0][0]的。

        ---

        class Solution {public:
            int minPathSum(vector>& grid) { int m = grid.size(), n = grid[0].size();
                vector> dp(m + 1, vector(n + 1, INT_MAX));
            
                dp[0][1] = 0, dp[1][0] = 0;    
                for (int i = 1; i <= m; i ++)
                { for (int j = 1; j <= n; j ++)
                    { dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i - 1][j - 1];
                    }
               }
               return dp[m][n];
            }
        };
        

        ---

        2. 地下城游戏🆗

        题目链接🔗

        ---

        • 🐧解题思路： 动态规划~路径问题

          🍎① 状态表示：

          dp[i][j] ：表示以 (i, j) 位置为起点，从(i，j)位置到终点所需健康点数的最小值。

           dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];
                      
                      // 注意：(i，j) 位置的健康值可能为正数，如果为正数的话，此时dp[i][j]求出来变成负数了
                      dp[i][j] = max(1, dp[i][j]);
          

          🖊为什么不能以 (i，j)位置为终点大家知道吗 ？

          🍎② 初始化：

          我们求的是最小值，所以初始化的时候，应该把dp初始化为INT_MAX，但是有两个特殊的点要初始化为1，dp[m][n - 1] = 1, dp[m - 1][n] = 1;

          因为dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j]; 终点位置的健康值要比 dungeon[m-1][n-1]至少大 1。

          ---

          class Solution {public:
              int calculateMinimumHP(vector>& dungeon) { int m = dungeon.size(), n = dungeon[0].size();
                  vector> dp(m + 1, vector(n + 1, INT_MAX));
                  dp[m][n - 1] = 1, dp[m - 1][n] = 1;
                  
                  // 从下往上
                  for (int i = m - 1; i >= 0; i --)
                  { // 从右往左
                      for (int j = n - 1; j >= 0; j --)
                      { dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];
                          
                          // 因为 (i, j)位置必须要始终保持 >= 1 
                          dp[i][j] = max(1, dp[i][j]);
                      }
                  }
                  return dp[0][0];
              }
          };