63. 不同路径II

题目描述：

一个机器人位于一个 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.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] 为 0 或 1

---

解题分析及思路：

此题为62、不同路径的进阶版本，与其唯一不同的是路上设置的路障。

对于机器人所在位置(i,j),因为此处可能会设有路障，那么机器人从到达此处有两种可能：

• 如果位置(i,j)设有路障🚧，那么则表示无法到达该位置，此时路径条数为0；
• 如果位置(i,j)未设有路障，那么则表示可以到达该位置，此时路径条数为该位置左方位置与上方位置条数之和。

所以对应的状态转移方程为：

f(i,j)=f(i−1,j)+f(i,j−1)		`(i,j)`未设有路障
f(i,j)=0										`(i,j)`设有路障🚧

那么对应动态规划解法：

1. 定义状态： 在这个问题中，状态可以定义为到达每个位置时的不同路径数量。我们使用二维数组 dp 表示状态，其中 dp[i][j] 表示到达网格位置 (i, j) 时的不同路径数量。

2. 找到状态转移方程： 机器人每次只能向下或者向右移动一步，因此到达当前位置 (i, j) 的不同路径数量等于到达上方位置 (i-1, j) 和到达左方位置 (i, j-1) 的路径数量之和。状态转移方程可以表示为：

dp[i][j] = dp[i-1][j] + dp[i][j-1]		obstacleGrid[i][j] == 1
dp[i][j] = 0													obstacleGrid[i][j] == 0

3. 初始化： 在初始化阶段，我们遍历第一行和第一列，将每个位置的路径数量初始化为1，因为机器人只能向下或向右移动，所以沿着第一行和第一列的路径数量都只有一种。并且在第一列某处设有路障之后，该列处于该处后续的位置均不可达，第一行也同理。

4. 递推求解： 通过嵌套循环遍历整个二维数组，根据状态转移方程计算每个位置的不同路径数量。

5. 计算最终结果： 最终结果即为到达右下角位置 (m-1, n-1) 时的不同路径数量。

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	m := len(obstacleGrid)
	n := len(obstacleGrid[0])
	dp := make([][]int, m)
	for i := 0; i < m; i++ {
		dp[i] = make([]int, n)
	}
	for i := 0; i < m; i++ {
		if obstacleGrid[i][0] == 1 {
			break
		}
		dp[i][0] = 1
	}
	for i := 0; i < n; i++ {
		if obstacleGrid[0][i] == 1 {
			break
		}
		dp[0][i] = 1
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if obstacleGrid[i][j] == 0 {
				dp[i][j] += dp[i-1][j] + dp[i][j-1]
			}
		}
	}
	return dp[m-1][n-1]
}

复杂度：

• 时间复杂度：O(M*N)，其中 M 为 m 的值，N 为 n 的值。
• 空间复杂度：O(M*N)，其中 M 为 m 的值，N 为 n 的值。

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:2.3 MB,击败了75.28% 的Go用户