leetcode | 63. Unique Paths Ⅱ

題目

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,1)

。

其中一種方法便是利用BFS廣度優先搜尋來模拟機器人所有可能行走的路徑，知道目前位置為地圖右下角時，路徑數量加1。這種方法的時間複雜度為 O ( M N ) O(MN) O(MN)。

此外，動态規劃也可以解決此題目：

我們要計算從

(1,1)

到達

(i,j)

位置的路徑數量，即為從

(1,1)

到達

(i-1,j)

和從

(1,1)

到達

(i,j-1)

的路徑數量之和。狀态轉移方程為：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

。

代碼實作（Go）

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    rows := len(obstacleGrid)
    cols := len(obstacleGrid[0])
    dp := make([][]int, 0)
	// dp資料初始化，預設為0
    for i:=0; i<=rows; i++ {
        row := make([]int, cols+1)
        dp = append(dp, row)
    }
    // 機器人從（1，1）位置到達（1，1）位置路徑數為1
    dp[1][1] = 1
    // 如果起點位置被障礙物所占用，則路徑數為0
    if obstacleGrid[0][0] == 1 {
        dp[1][1] = 0
    }
    // 遞推計算（1，1）到達（i，j）的路徑數
    for i:=1; i<=rows; i++ {
        for j:=1; j<=cols; j++ {
            if obstacleGrid[i-1][j-1] == 0 && !(i==1 && j==1) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            }
        }
    }
    return dp[rows][cols]
}
           

遇到的問題

動态規劃的難度主要在于狀态轉移方程，其次是dp數組的初始化。我們需要根據具體情況，對dp進行合理的初始化。在此題目中，一般情況下

dp[1][1]=1

，這也符合我們的認知；另一方面，如果（1，1）為障礙物所占用，則說明機器人不存在，則

dp[1][1]=0

。