Unique Paths II

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?

An obstacle and empty space is marked as1and0respectively 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

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

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

for row 0

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

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

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和LC 63 Unique Paths II

• 这篇文章的代码在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