# 63     Unique Paths II

## 63. [Unique Paths II](https://leetcode.com/problems/unique-paths-ii/description/)

## 1. Question

A robot is located at the top-left corner of a\_m\_x\_n\_grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

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.

**Note:**\_m\_and\_n\_will be at most 100.

**Example 1:**

```
Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

Output: 2

Explanation:

There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
```

## 2. Implementation

**(1) DP**

思路: 在第一行和第一列走只有1种走法，所以对此我们要特殊处理，f(i,j)表示走到cell(i, j)的走法，则状态转移方程为:

f(i,j) = f(i - 1, j) + f(i, j - 1) if obstacle\[i]\[j] != 1

f(i,j) = 0 if obstacle\[i]\[j] == 1

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

        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];

        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) {
                break;
            }
            dp[i][0] = 1;
        }

        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] == 1) {
                break;
            } 
            dp[0][j] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}
```

## 3. Time & Space Complexity

**DP**: 时间复杂度O(mn), 空间复杂度O(mn)