一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
示例 1:
1
2
3
4
5
6
7
8
9
10
11
12
| 输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
|
此题相比 不同路径 多了一个障碍物判断。第一行第一列中只要有一个障碍物，后面的路径数全部为 0 。如果位置 (i,j) 上有障碍物，则路径数直接为 0 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid.length;
int m = obstacleGrid[0].length;
int[][] counts = new int[n][m];
for(int i=0; i<n; ++i){
if(obstacleGrid[i][0] == 1){
break;
}
else{
counts[i][0] = 1;
}
}
for(int i=0; i<m; ++i){
if(obstacleGrid[0][i] == 1){
break;
}else{
counts[0][i] = 1;
}
}
for(int i=1; i<n; ++i){
for(int j=1; j<m; j++){
if(obstacleGrid[i][j] == 1){
counts[i][j] = 0;
}
else{
counts[i][j] = counts[i-1][j]+counts[i][j-1];
}
}
}
return counts[n-1][m-1];
}
}
|
时间复杂度为O(mn)，空间复杂度为 O(mn)。
我们可以继续对空间复杂度优化，可以看出 dp 方程中只与上一行的元素和左边元素有关，我们可以只使用一个一维数组存储数据。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[]counts = new int[n];
paths[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(obstacleGrid[i][j] == 0){
if(j > 0){
counts[j] += counts[j - 1];
}
}else{
counts[j] = 0;
}
}
}
return counts[n - 1];
}
}
|
时间复杂度为O(mn)，空间复杂度为 O(n)。