# Unique Paths II

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

`Dynamic Programming`

**Medium**

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?

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

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
```

### Analysis

1 . **状态 State**

`dp[i][j]`- the number of paths from origin to position (i, j)

2 . **方程 Function**

```java
if (obstacleGrid[i][j] == 1) {
    dp[i][j] = 0;
} else {
    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
```

3 . **初始化 Initialization**

for column 0

```java
if (obstacleGrid[i][0] == 0 && dp[i - 1][0] > 0) {
    dp[i][0] = 1;
} else {
    dp[i][0] = 0;
}
```

for row 0

```java
if (obstacleGrid[0][j] == 0 && dp[0][j - 1] > 0) {
    dp[0][j] = 1;
} else {
    dp[0][j] = 0;
}
```

4 . **答案 Answer**

`dp[m - 1][n - 1]`- namely the destination

### Solution

DP - O(mn) space, O(mn) time

```java
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || 
            obstacleGrid.length == 0 || 
            obstacleGrid[0].length == 0 || 
            obstacleGrid[0][0] == 1) {
            return 0;
        } 
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 1; i < m; i++) {
            if (obstacleGrid[i][0] == 0 && dp[i - 1][0] > 0) {
                dp[i][0] = 1;
            } else {
                dp[i][0] = 0;
            }
        }
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[0][j] == 0 && dp[0][j - 1] > 0) {
                dp[0][j] = 1;
            } else {
                dp[0][j] = 0;
            }
        }
        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];

    }
}
```

DP - Space optimized - O(n) space, O(mn) time

```java
class Solution {
 public int uniquePathsWithObstacles(int[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0|| grid[0][0] == 1) {
        return 0;
    }
    int m = grid.length, n = grid[0].length;
    int[] dp = new int[n];
    dp[0] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                dp[j] = 0;
            } else {
                dp[j] += (j > 0) ? dp[j - 1] : 0;
            }
        }
    }
    return dp[n - 1];
}   
}
```

> `dp[j] += dp[j - 1];`
>
> is
>
> `dp[j] = dp[j] + dp[j - 1];`
>
> which is
>
> `new dp[j] = old dp[j] + dp[j-1]`
>
> which is
>
> `current cell = top cell + left cell`

## Unique Paths - Follow Up

by **@ jaychsu**

<https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=423857&extra=&page=1&_dsign=2a102aab>

> 给定一个矩形的宽和长，求所有可能的路径数量
>
> Rules：
>
> 1. 从左上角走到右上角
> 2. 要求每一步只能向正右、右上或右下走，即 →↗↘
>
> followup1: 优化空间复杂度至 O(n)
>
> followup2: 给定矩形里的三个点，判断是否存在遍历这三个点的路经
>
> followup3: 给定矩形里的三个点，找到遍历这三个点的所有路径数量
>
> followup4: 给定一个下界 (x == H)，找到能经过给定下界的所有路径数量 (x>= H)
>
> followup5: 起点和终点改成从左上到左下，每一步只能 ↓↘↙，求所有可能的路径数量

在往下看之前：

* 希望你已经先做过[LC 62 Unique Paths](https://leetcode.com/problems/unique-paths/description/)和[LC 63 Unique Paths II](https://leetcode.com/problems/unique-paths-ii/description/)
* 这篇文章的代码在<https://github.com/jaychsu/algorithm/blob/master/other/unique_paths_with_followups.py>
* Test Case 在 Comment 中以 \`>>>\` 和 \`...\` 开头，要跑 Test Case 可以拉下来在项目根目录输入 \`python -m doctest -v other/unique\_paths\_with\_followups.py\`
* 为了跟 print 的结果看起来一致，以下 dp\[x]\[y] 表示 (x, y)，也就是 x 是垂直的，y 是水平的

#### 从左上角走到右上角，要求每一步只能向正右、右上或右下走，即 →↗↘

* 代码：L16-L48,

  <https://github.com/jaychsu/algorithm/blob/c6f6c8e81aad557b8bc520b1a9298d201462c20f/other/unique_paths_with_followups.py#L16-L48>
* 刚看到题目可能觉得需要什么特殊的方法，然而并没有
* 遍历顺序需要换一下，因为每个格子只能从左方，左上，左下过来，也就是必须把 dp\[x]\[j - 1] 的所有格子算好，才能继续算 dp\[x]\[j]

#### followup1: 优化空间复杂度至 O(n)

* 代码：L51-L86,

  <https://github.com/jaychsu/algorithm/blob/c6f6c8e81aad557b8bc520b1a9298d201462c20f/other/unique_paths_with_followups.py#L51-L86>
* 可以把 dp\[m]\[n] 简化成 dp\[m]，但是如果直接往 dp\[x] 上加，会挂。挂的原因是 dp 需要加上 dp\[i + 1] 和 dp\[i - 1]，但是当到下一格的时候 dp\[x] (x == i + 1)，dp\[x] 需要往回加 dp，而 dp 已经事先加过 dp\[x] 了，所以 dp\[x] 又会加一次自己原来的值，所以出错
* 解法就是在进每个格子之后，先用个变量保存 dp\[x] 的值，然后再 modify dp\[x]，等到下一格 dp\[x + 1] 要往回加的时候，就去加这个临时变量
* 也可以用滚动数组弄成 dp\[m]\[2]

#### followup2: 给定矩形里的三个点，判断是否存在遍历这三个点的路经

* 代码：L89-L127,

  <https://github.com/jaychsu/algorithm/blob/c6f6c8e81aad557b8bc520b1a9298d201462c20f/other/unique_paths_with_followups.py#L89-L127>
* 画图观察就能发现规律。因为从每一格只能走三个方向，考虑两个格子 (x, y) 和 (i, j)，当 (x, y) 能走到 (i, j) 的时候，(x, y) 会位于 (i, j) 向后张的扇形面积里面
* 用式子表达就是，i - dy <= x <= i + dy, where dy = j - y
* 排序（这边可以先想想怎么排序）之后只要发现一组不满足就不存在

#### followup3: 给定矩形里的三个点，找到遍历这三个点的所有路径数量

* 代码：L130-L187,

  <https://github.com/jaychsu/algorithm/blob/c6f6c8e81aad557b8bc520b1a9298d201462c20f/other/unique_paths_with_followups.py#L130-L187>
* 感觉没有什么特殊的，唯一的区别就是在算完 y - 1 之后，要进 y 之前，把非必经点归零

#### followup4: 给定一个下界 (x == H)，找到能经过给定下界的所有路径数量 (x >= H)

* 代码：L190-L242,

  <https://github.com/jaychsu/algorithm/blob/c6f6c8e81aad557b8bc520b1a9298d201462c20f/other/unique_paths_with_followups.py#L190-L242>
* 思路是先做一遍正常的，接着把低于 H 的归零，然后再从 x == H 遍历到终点

#### followup5: 起点和终点改成从左上到左下，每一步只能 ↓↘↙，求所有可能的路径数量

* 代码：L245-L277,

  <https://github.com/jaychsu/algorithm/blob/c6f6c8e81aad557b8bc520b1a9298d201462c20f/other/unique_paths_with_followups.py#L245-L277>