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: 起点和终点改成从左上到左下,每一步只能 ↓↘↙,求所有可能的路径数量

在往下看之前:

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

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: 给定矩形里的三个点,判断是否存在遍历这三个点的路经

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

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

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

results matching ""

    No results matching ""