LeetCode 63. Unique Paths II 不同的路径 II

题目

https://leetcode.com/problems/unique-paths-ii/description/

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as `1` and `0` respectively in the grid.

For example,

There is one obstacle in the middle of a 3×3 grid as illustrated below.

```[
[0,0,0],
[0,1,0],
[0,0,0]
]
```

The total number of unique paths is `2`.

Note: m and n will be at most 100.

Java参考代码

```class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
return 0;
}

int height = obstacleGrid.length;
int width = obstacleGrid[0].length;

int[][] paths = new int[height][width];

// first column
for (int i = 0; i < height; i++) {
if (obstacleGrid[i][0] != 1) {
paths[i][0] = 1;
} else {
break;
}
}

// first row
for (int j = 0; j < width; j++) {
if (obstacleGrid[0][j] != 1) {
paths[0][j] = 1;
} else {
break;
}
}

// for spaces not at first row or first column
for (int i = 1; i < height; i++) {
for (int j = 1; j < width; j++) {
if (obstacleGrid[i][j] != 1) {
paths[i][j] = paths[i - 1][j] + paths[i][j - 1];
}
}
}

return paths[height - 1][width - 1];
}
}```