华为 OD 训练营 · 题解精讲
LC63. 不同路径 II
配套讲解：视频讲解 ↗
LC63. 不同路径 II 视频地址：https://uha.xet.tech/s/1JKdYz
题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 现在考虑网格中有障碍物。问总共有多少条不同的路径？ XMuYbSCIyo2aW0xkLzrcDzarnVh.png
网格中的障碍物和空位置分别用 1 和 0 来表示。 KrARbadunofZ0Qxl7Lmc5suMnNb.png
题目解析
解题思路
本题是带障碍物的网格路径计数问题，机器人只能向右或向下移动。采用动态规划求解，定义 dp[i][j] 表示从起点 (0,0) 到达 (i,j) 的不同路径数。
状态转移方程：
- 若
(i,j)是障碍物，则dp[i][j] = 0（不可达）。 - 否则，
dp[i][j] = dp[i-1][j] + dp[i][j-1]，因为只能从上方或左方到达。
边界初始化：
- 第一行：只能从左向右移动，遇到障碍物前
dp[0][j] = 1，障碍物及其后均为 0。 - 第一列：只能从上向下移动，同理处理。
关键步骤
1. 初始化第一行和第一列
第一行: [1, 1, 0, 0] (第2列有障碍，后续全0)
第一列: [1, 0, 0, 0] (第1行有障碍，后续全0)2. 填充剩余格子 从 (1,1) 开始遍历，若当前格子不是障碍物，则累加上方和左方的 dp 值。 例如 dp[1][1] = dp[0][1] + dp[1][0]。
3. 返回结果 最终 dp[m-1][n-1] 即为答案。
复杂度分析
- 时间复杂度：O(m×n)，遍历整个网格一次。
- 空间复杂度：O(m×n)，使用二维 dp 数组存储状态。
参考代码
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
# 设置二维数组 dp 用来储存到达每个位置时不同路径的数量
# dp[0][0] 表示从第 0 行第 0 列到达第 0 行第 0 列时不同路径的数量
# dp[0][i] 表示从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
# dp[j][0] 表示从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
# dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
# m 行
m = len(obstacleGrid)
# n 列
n = len(obstacleGrid[0])
dp = [[0] * n for _ in range(m)]
# i 从 0 遍历到 m - 1
# 获取从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
# 由于每次只能向下或者向右移动一步，此时只能向下移动一步
# 所以，只能一直向下走，只有这一条路径
for i in range( 0 , m ):
# 一旦出现了障碍，那么后面所有的位置都是到达不了的，都是默认的 0
if obstacleGrid[i][0] == 1 : break
# 仅此一条，别无分路
dp[i][0] = 1
# j 从 0 遍历到 n - 1
# 获取从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
# 由于每次只能向下或者向右移动一步，此时只能向右移动一步
# 所以，只能一直向右走，只有这一条路径
for j in range( 0 , n ):
# 一旦出现了障碍，那么后面所有的位置都是到达不了的，都是默认的 0
if obstacleGrid[0][j] == 1 : break
# 仅此一条，别无分路
dp[0][j] = 1
# 接下来从第 1 行到第 m - 1 行
# 从第 1 列到 n - 1 列
# 填充二维数组 dp 里面的值
# dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
for i in range( 1 , m ):
for j in range( 1 , n ):
# 由于每次只能向下或者向右移动一步
# 如果此时出现了障碍，那么由于无法到达这个位置，因此不用处理
if obstacleGrid[i][j] == 1 : continue
# 位置 (i,j) 的不同路径的数量是由
# 1、上边位置 dp[ i - 1 ][j] 的不同路径的数量
# 2、左边位置 dp[i][ j - 1 ] 的不同路径的数量
# 两者之和获取到的
dp[i][j] = dp[ i - 1 ][j] + dp[i][ j - 1 ]
# dp[ m - 1][ n - 1 ] 表示从第 0 行第 0 列到达第 m - 1 行第 n - 1 列时不同路径的数量
# 即到达终点的数量
# 返回这个结果即可
return dp[ m - 1 ][ n - 1 ]