难度: Medium
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
示例 2：
输入：obstacleGrid = [[0,1],[0,0]] 输出：1
提示：
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j] 为 0 或 1运行时间: 48 ms
内存: 15 MB
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
memo = dict()
def dp(i, j):
if i < 0:
return 0
if j < 0:
return 0
if i == 0 and j == 0:
if obstacleGrid[0][0] == 1:
return 0
else:
return 1
if (i, j) in memo:
return memo[(i, j)]
res = 0
if obstacleGrid[i-1][j] == 0:
res += dp(i-1, j)
if obstacleGrid[i][j-1] == 0:
res += dp(i, j-1)
memo[(i, j)] = res
return res
if obstacleGrid[len(obstacleGrid)-1][len(obstacleGrid[0])-1] == 1:
return 0
else:
return dp(len(obstacleGrid)-1, len(obstacleGrid[0])-1)
这个题解使用动态规划的思路来解决问题。通过备忘录的方式，自底向上地计算从起点到终点的路径数。对于网格中的每个位置，如果该位置没有障碍物，那么到达该位置的路径数等于到达其上方位置的路径数加上到达其左方位置的路径数。在计算过程中，通过备忘录避免重复计算，提高效率。最终返回到达终点的路径数作为结果。
时间复杂度: O(m*n)
空间复杂度: O(m*n)
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
memo = dict()
def dp(i, j):
# 处理越界情况
if i < 0:
return 0
if j < 0:
return 0
# 处理起点情况
if i == 0 and j == 0:
if obstacleGrid[0][0] == 1:
return 0
else:
return 1
# 检查备忘录中是否已有计算结果
if (i, j) in memo:
return memo[(i, j)]
res = 0
# 如果上方位置没有障碍物，则加上从上方到达当前位置的路径数
if obstacleGrid[i-1][j] == 0:
res += dp(i-1, j)
# 如果左方位置没有障碍物，则加上从左方到达当前位置的路径数
if obstacleGrid[i][j-1] == 0:
res += dp(i, j-1)
# 将计算结果存入备忘录
memo[(i, j)] = res
return res
# 如果终点有障碍物，则无法到达，返回0
if obstacleGrid[len(obstacleGrid)-1][len(obstacleGrid[0])-1] == 1:
return 0
else:
# 从终点开始递归计算路径数
return dp(len(obstacleGrid)-1, len(obstacleGrid[0])-1)
在动态规划中，我们需要从已知的基础情况（如起点或边界）出发，逐步建立到达更复杂位置的路径计算。在递归函数dp中，检查(i-1, j)和(i, j-1)的位置是为了根据已解决的子问题（这些子问题即到达上方和左方位置的路径数）来解决当前问题（即到达位置(i, j)的路径数）。该方法假设这些子问题已经被解决，所以在尝试计算当前位置的路径数之前，需要先获得这些必需的子问题的解。
是的，如果位置(i, j)本身有障碍物，则应该直接返回0。在题解中，这一点应该在读取位置(i, j)的障碍物信息之后立即检查，因为如果当前位置不可通过，则不需要继续计算从上方或左方到达当前位置的路径数。这不仅避免了不必要的计算，也符合实际情况，即障碍物阻止了任何路径通过该位置。
备忘录memo使用字典而不是二维数组的主要原因是灵活性和空间效率。字典允许我们仅保存那些实际进行了计算的状态，从而在稀疏网格（大部分位置有障碍物的情况）中节省空间。相比之下，二维数组会为整个网格的每个位置分配空间，包括那些根本不会被访问的位置。因此，使用字典可能会在空间使用上更有效，尤其是在大规模或稀疏的网格中。
处理边界情况时，需要特别注意i=0或j=0的情况。如果在边界行或列中存在障碍物，那么从该障碍物之后的所有位置都应该被视为无法到达。在递归函数中，可以通过检查边界行或列中每个位置是否存在障碍物，并据此更新路径计数来处理此问题。例如，如果第0行的某个位置j有障碍物，则该位置及其右侧的所有位置的路径数都应该是0。同理，对于第0列也应当如此处理。