LeetCode 63. 不同路径 II — Python3 实现思路在 [62. 不同路径] 的基础上加入障碍物如果obstacleGrid[i][j] 1有障碍则dp[i][j] 0否则dp[i][j] dp[i-1][j] dp[i][j-1]解法一原地 DP推荐直接在输入数组上修改obstacleGrid[i][j]变为到该格的路径数空间 O(1)fromtypingimportListclassSolution:defuniquePathsWithObstacles(self,obstacleGrid:List[List[int]])-int:ifobstacleGrid[0][0]1:return0m,nlen(obstacleGrid),len(obstacleGrid[0])obstacleGrid[0][0]1# 起点路径数为 1# 初始化第一列障碍物之前为 1之后全为 0foriinrange(1,m):obstacleGrid[i][0]int(obstacleGrid[i][0]0andobstacleGrid[i-1][0]1)# 初始化第一行同理forjinrange(1,n):obstacleGrid[0][j]int(obstacleGrid[0][j]0andobstacleGrid[0][j-1]1)# 填充其余部分foriinrange(1,m):forjinrange(1,n):ifobstacleGrid[i][j]0:obstacleGrid[i][j]obstacleGrid[i-1][j]obstacleGrid[i][j-1]else:obstacleGrid[i][j]0returnobstacleGrid[m-1][n-1]解法二一维 DP更简洁dp[j]表示当前行第j列的路径数fromtypingimportListclassSolution:defuniquePathsWithObstacles(self,obstacleGrid:List[List[int]])-int:nlen(obstacleGrid[0])dp[0]*n dp[0]1# 起点forrowinobstacleGrid:forjinrange(n):ifrow[j]1:dp[j]0elifj0:dp[j]dp[j-1]returndp[n-1]示例验证输入[[0,0,0],[0,1,0],[0,0,0]]答案 2起点 dp [1, 0, 0] 第1行 [0,0,0]: dp [1, 1, 2] 第2行 [0,1,0]: 障碍物处 dp[1]0得 dp [1, 0, 1] 第3行 [0,0,0]: dp [1, 1, 2] 返回 dp[2] 2 ✅边界情况起点或终点有障碍物时自动返回 0起点dp[0]1会在第一轮循环中被清零。复杂度两种解法均为时间 O(m×n)解法一空间 O(1)解法二空间 O(n)。推荐解法二代码最短且逻辑清晰。