# 62 & 63. Unique Paths I & II

**62. Unique Paths**

There is a robot on an `m x n` grid. The robot is initially located at the **top-left corner** (i.e., `grid[0][0]`). The robot tries to move to the **bottom-right corner** (i.e., `grid[m - 1][n - 1]`). The robot can only move either down or right at any point in time.

Given the two integers `m` and `n`, return *the number of possible unique paths that the robot can take to reach the bottom-right corner*.

The test cases are generated so that the answer will be less than or equal to `2 * 109`.

**Example 1:**

![](https://assets.leetcode.com/uploads/2018/10/22/robot_maze.png)

<pre><code><strong>Input: m = 3, n = 7
</strong><strong>Output: 28
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: m = 3, n = 2
</strong><strong>Output: 3
</strong><strong>Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
</strong>1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
</code></pre>

***My Solutions:***

用一个dp\[]\[]记录可以走到每一步的解法。

```
public int uniquePaths(int m, int n) {
    if (m == 0 || n == 0) return 0;
    if (m == 1 || n == 1) return 1;
    int[][] dp = new int[m][n];

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 || j == 0) dp[i][j] = 1; // 第一行和第一列只有一种到达的方法
            else dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // 其他位置有从上或从左到达的方法
        }
    }

    return dp[m - 1][n - 1];
}
```

**63. Unique Paths II**

You are given an `m x n` integer array `grid`. There is a robot initially located at the top-left corner (i.e., `grid[0][0]`). The robot tries to move to the **bottom-right corner** (i.e., `grid[m - 1][n - 1]`). The robot can only move either down or right at any point in time.

An obstacle and space are marked as `1` or `0` respectively in `grid`. A path that the robot takes cannot include **any** square that is an obstacle.

Return *the number of possible unique paths that the robot can take to reach the bottom-right corner*.

The testcases are generated so that the answer will be less than or equal to `2 * 109`.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/11/04/robot1.jpg)

<pre><code><strong>Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
</strong><strong>Output: 2
</strong><strong>Explanation: There is one obstacle in the middle of the 3x3 grid above.
</strong>There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
</code></pre>

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/11/04/robot2.jpg)

<pre><code><strong>Input: obstacleGrid = [[0,1],[0,0]]
</strong><strong>Output: 1
</strong></code></pre>

**Constraints:**

* `m == obstacleGrid.length`
* `n == obstacleGrid[i].length`
* `1 <= m, n <= 100`
* `obstacleGrid[i][j]` is `0` or `1`.

My Solutions:

和上题类似，但因为有障碍，因此不能认为第一行和第一列的每个格子一定能到达，需要先单独处理第一列和第一行。第一行从左到右和第一列从上到下的时候，如果碰到一个障碍，当前格子和剩下的格子只能先空着。在遍历其他格子的时候，如果碰到障碍，走到这里的走法设置为0.

```
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    if (obstacleGrid == null) return 0;
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;
    if (m == 0 || n == 0 
        || obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0;

    int[][] dp = new int[m][n];

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

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

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[i][j] == 1) dp[i][j] = 0;
            else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    return dp[m - 1][n - 1];
}
```