Leetcode63：不同路径II

题目描述：

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

测试用例保证答案小于等于 2*10^9。

代码思路： 边界条件检查： 首先检查终点（右下角）和起点（左上角）是否有障碍物。如果起点或终点有障碍物，则无法到达终点，直接返回0。 初始化变量： m = len(obstacleGrid)：获取网格的行数。n = len(obstacleGrid[0])：获取网格的列数。dp = [[0] * n for _ in range(m)]：创建一个二维数组dp，用于存储到达每个格子的不同路径数。数组的大小与输入的网格相同。 填充动态规划数组： 使用两个嵌套的for循环遍历网格的每个格子。对于每个格子(i, j)： 如果该格子有障碍物（obstacleGrid[i][j] == 1），则无法到达该格子，设置dp[i][j] = 0。否则，根据格子的位置来更新dp[i][j]的值： 如果格子是起点（(i, j) == (0, 0)），则只有一条路径到达该格子（即它自己），设置dp[i][j] = 1。如果格子在第一行（i == 0），则只能从左边的格子到达，因此dp[i][j] = dp[i][j - 1]。如果格子在第一列（j == 0），则只能从上面的格子到达，因此dp[i][j] = dp[i - 1][j]。对于其他格子，可以从上面的格子或左边的格子到达，因此dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。 返回结果： 最后，dp[-1][-1]存储了从左上角到右下角的不同路径数，返回该值作为结果。 代码实现： class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: #dp[m][n] = dp[m - 1][n] + dp[m][n - 1] if obstacleGrid[-1][-1] or obstacleGrid[0][0]: return 0 m = len(obstacleGrid) n = len(obstacleGrid[0]) dp = [[0] * n for _ in range(m)] for i in range(m): for j in range(n): if obstacleGrid[i][j] == 1: dp[i][j] = 0 else: if i == j == 0: dp[i][j] = 1 elif i == 0: dp[i][j] = dp[i][j - 1] elif j == 0: dp[i][j] = dp[i - 1][j] else: dp[i][j] = dp[i - 1][j] + dp[i][j - 1] return dp[-1][-1]