1.1. 题目
1.1.1. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
1.1.2. 题解:
- 题目跟之前那个
不同路径是差不多的!不过有区别是这个有障碍 - 障碍的标记点为
1,所以可以根据值确定该点是不是障碍点 - 障碍点右边和下边的点 可能只有一个方向来!
1.1.3. 思路:
- 还是动归,还是记录每个点的路径的可能性
- 一旦遇到障碍点,障碍点的路径可能性 设置为 0,这样其他获得左边+上面的和时候,就不需要考虑左/上边是不是障碍点了!
- 但是要注意: 如果是 x轴或者y轴有个障碍点,比如x轴有个障碍点,那么这个障碍点右边的路径都是0, 比如 [0,1,0,0,0],
1右边所有的路径可能性都是0 - 如果y轴有一个障碍点,同理,该障碍点下面的所有点的路径可能性都是
0
1.1.4. 代码:
点击显示
n := len(obstacleGrid)
m := len(obstacleGrid[0])
dp := make([][]int,n)
for i:=0;i<n;i++ {
dps := make([]int,m)
for j:=0;j<m;j++ {
if obstacleGrid[i][j] == 1 {
dps[j] = 0
dp[i] = dps
continue
}
if j == 0 && i == 0 {
dps[0] = 1
dp[i] = dps
continue
}
if i == 0 {
dps[j] = dp[i][j-1]
dp[i] = dps
continue
}
if j == 0 {
dps[j] = dp[i-1][j]
dp[i] = dps
continue
}
dps[j] = dp[i-1][j] + dp[i][j-1]
dp[i] = dps
}
}
return dp[n-1][m-1]