> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/zou-ge/unique_paths_ii.md).

# Unique Paths II

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

**Easy** Follow up for "Unique Paths":

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.

## Thoughts

相比起I需要对有石头的地方特殊处理一下. 石头代表那个点无路可达，值为0. 需要特别注意的是当石头出现在首行或首列时，后面的路都不再可达。

给定M\*N的矩阵G,

设Fi,j为从(0, 0)处往下或往右走到(i, j)处的unique path的数目, 当G(i, j) = 1时Fi,j = 0. 求F(M-1, N-1).

## Code

```
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid[0].length;
        int[] f = new int[n];
        f[0] = 1;
        for (int[] row : obstacleGrid) {
            for (int j = 0; j < n; j++) {
                if (row[j] == 1) {
                    f[j] = 0;
                } else if (j > 0) {
                    f[j] += f[j - 1];
                }
            }
        }

        return f[n - 1];
    }
}
```

## Analysis

做题耗时: 10min

Errors:

1. 没有把首行或者首列石头后的置为0.

TC: O(mn)