Description

Unique Paths II

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

给出地图，求左上角到右下角的路径数量（只能向下或向右移动）。

其中地图中1表示障碍，无法通过。

Solution

动态规划（Dynamic Programming）

要到达最后一个格子，只能通过它左边和上边两个格子到达， 那么达到它的路径数量等于到达左边和上边两个格子的路径数量相加。

依此类推，到达左边和上边两个格子的路径数量又分别等于它们的左边和上边两条路径之和。

最终我们将反推到第一个格子，它的路径数量只有一条。

其中第一排和第一列稍微特殊，它们只有一条路径可以到达。

所以当前格子路径数量：

$$ f(x, y) = f(x-1, y) + f(x, y-1) $$

通过这个公式可以写出对应的递归方法。

更简便的方法是从左上方格子开始，向后计算每个格子的路径数量，直到最后一个格子。

Example

比如地图4x3的地图，将第一个格子路径数量标记为1，然后依次标记后边的格子，得到达到最后一个格子的路径数量为10：

0, 0, 0, 0       1, 1, 1, 1
0, 0, 0, 0  ==>  1, 2, 3, 4
0, 0, 0, 0       1, 3, 6, 10

现在假设有一个障碍，只需要在遇到障碍时，将障碍的路径数量标记为0即可：

0, 0, 0, 0       1, 1, 1, 1
0, 0, 1, 0  ==>  1, 2, 0, 1
0, 0, 0, 0       1, 3, 3, 4

Code Here

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    row := len(obstacleGrid)
    if row == 0 {
        return 0
    }

    col := len(obstacleGrid[0])
    if col == 0 || obstacleGrid[0][0] == 1 {
        return 0
    }

    var left, up int
    var ways int

    // 标记第一格到达路径数量为1
    obstacleGrid[0][0] = 1
    j := 1 // 从第二个格子开始
    for i := 0; i < row; i++ {
        for ; j < col; j++ {
            // 如果为障碍，标记当前格子达到路径数量为 0
            if obstacleGrid[i][j] == 1 {
                obstacleGrid[i][j] = 0
                continue
            }

            // 表示当前格子到达路径数量
            // 它等于左边格子路径数量+上边格子路径数量
            ways = 0

            left = j - 1
            if left >= 0 {
                // 加上左边格子路径数量
                // ways += leftWays
                ways = obstacleGrid[i][left]
            }

            up = i - 1
            if up >= 0 {
                // 加上上边格子路径数量
                ways += obstacleGrid[up][j]
            }

            // 保存当前格子路径数量
            obstacleGrid[i][j] = ways
        }
        j = 0
    }

    // 返回最后一个格子路径数量
    return obstacleGrid[row-1][col-1]
}

Similar Problem