6、矩形路径

62. 不同路径——基础类型

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

img

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

思路

dp[i][j]：表示着到达i，j位置一共有dp[i][j]种方法

dp[i][j]一共有几种方式可以到达

上方或者是左方

`dp[i][j] = dp[i-1][j] + dp[i][j-1]`

初始化：

`dp[0][j], dp[i][0] = 1, 1`

遍历顺序：从左到右，从上到下

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        """
        dp[i][j]：表示着到达i，j位置一共有dp[i][j]种方法

        dp[i][j]一共有几种方式可以到达
        上方或者是左方
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
        初始化：
            dp[0][j], dp[i][0] = 1, 1
        遍历顺序：从左到右，从上到下
        """
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1

        for i in range(1, m):
            for j in range(1,n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        print(dp) 
        return dp[-1][-1]

63. 不同路径 II——障碍物版本

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

img

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

img

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

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

思路和递推公式基本一致，只是初始化不一样，增加点判断条件

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if not obstacleGrid:
            return 0

        m = len(obstacleGrid)
        n = len(obstacleGrid[0])

        dp = [[0] * n for _ in range(m)]
        for j in range(n):
            if obstacleGrid[0][j] == 1:
                break
            else:
                dp[0][j] = 1

        for i in range(m):
            if obstacleGrid[i][0] == 1:
                break
            else:
                dp[i][0] = 1
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    continue
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        print(dp)
        return dp[-1][-1]

64. 最小路径和——路径和

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

**说明：**每次只能向下或者向右移动一步。

示例 1：

img

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

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

思路：

这道题求得是到达右下角的最短路径，（ij）的位置只能从(i-1, j)和(im j-1)得来，那么如何得来呢 (i-1, j)+grid[i][j] (i, j-1)+grid[i][j]

递归五部曲：

• 确定dp数组含义:dp[i][j]到达(i,j)位置的最小路径
• 递推公式：dp[i][j]=min(dp[i-1][j], dp[i][j-1])+grid[i][j]
• 初始化：首行首列需要递加求和
• 遍历顺序：从左到右，从上到下正序即可
• 打印

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        dp = [[0] * n for _ in range(m)]
        # dp[i][j] = min(dp[i-1][j]+grid[i][j], dp[i][j-1]+grid[i][j])
        dp[0][0] = grid[0][0]
        for j in range(1, n):
            dp[0][j] = dp[0][j - 1] + grid[0][j]
        for i in range(1, m):
            dp[i][0] = dp[i - 1][0] + grid[i][0]
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j])
        return dp[-1][-1]

174. 地下城游戏

恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。

返回确保骑士能够拯救到公主所需的最低初始健康点数。

**注意：**任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

示例 1：

img

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

示例 2：

输入：dungeon = [[0]]
输出：1

思路：

一开始我想的是从左上角到右下角进行遍历

但是这里有个问题就是我们一开始初始化这个左上角的值后，我们在遍历的过程中需要不断的更新我们初始化的值，这样是非常麻烦的。

因此我们可以从右下角往左上角进行遍历。

我们这里需要确保每个格子的初始hp都是1，初始化的就是1，和前一个格子-当前格子的血量取最大值

遍历顺序是从下往上，从右到左，也就是倒叙

动规五部曲

• 确定dp数组含义：dp[i][j]到达i，j位置需要的最小血量

• dp公式：dp[i][j] = max(min(dp[i + 1][j], dp[i][j + 1])- dungeon[i][j], 1)前一个格子的最小血量减去当前格子的血量，且最小值为1

• 初始化：

  • dp[0][0]最后一个格子的需要的血量 max(1-dungeon[i][j], 1)
  • dp[-1][j] = max(1, dp[-1][i + 1] - dungeon[-1][i])
  • dp[i][-1] = max(1, dp[i + 1][-1] - dungeon[i][-1])

• 遍历顺序倒序

  for i in range(m - 2, -1, -1):
  for j in range(n - 2, -1, -1):
  

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        if not dungeon:
            return 0
        m = len(dungeon)
        n = len(dungeon[0])

        dp = [[0] * (n) for _ in range(m)]
        dp[-1][-1] = max(1, 1 - dungeon[-1][-1])

        for i in range(n - 2, -1, -1):
            dp[-1][i] = max(1, dp[-1][i + 1] - dungeon[-1][i])
        for i in range(m - 2, -1, -1):
            dp[i][-1] = max(1, dp[i + 1][-1] - dungeon[i][-1])

        for i in range(m - 2, -1, -1):
            for j in range(n - 2, -1, -1):
                temp = min(dp[i + 1][j], dp[i][j + 1])
                dp[i][j] = max(temp - dungeon[i][j], 1)
        print(dp)
        return dp[0][0]