DP動態規劃 深入淺出 以Unique Path II 路徑總數II 為例

上次學過2D DP入門題目 Unique Path，接著來看進階一點的高度關聯延伸題
Unique Path II，這次板子上多了障礙物。

題目給定我們一個棋盤的高與寬，起點固定在左上角，終點固定在右下角。

每一步只能選擇往右走一格，或者往下走一格，不能回頭。

有障礙物的格子無法通過。

要求我們求出從起點到終點有幾條路徑。

詳細的題目可在這裡看到

測試範例:

Example 1:

Input: obstacleGrid = [[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

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

約束條件:

Constraints:

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] is 0 or 1.

同樣地，先走過一遍解題框架可分為三大步驟，藉此鞏固解題基礎。

1. 定義狀態 [我在哪裡]

通常遇到這種棋盤式或者帶有點座標的題目，定義一個二維狀態的DP是一種很常見且直觀的選擇。

這裡，我們可以定義DP[x, y] 為從起點(0,0)到座標(x,y)的路徑數目(方法數)。

那麼，最後我們要計算的就是DP[終點x座標, 終點y座標] = DP[ n-1, m-1]

2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]

不難發現，除了最上面的那一條row，和最左的那一條column之外，

中間的點座標都有兩種選擇(往右或往下)，反過來說，

中間的點座標可以從上面走過來，或者從左邊走過來。

所以，推廣到一般化的通式，對點座標(x, y)而言

DP[ x, y]

= 從起點左上角(0, 0)到點座標(x, y)的方法數

= 從起點左上角(0, 0)到點座標(x-1, y)的方法數 + 從起點左上角(0, 0)到點座標(x, y-1)的方法數

= DP[x-1, y] + DP[x, y-1]

3. 釐清初始狀態(終止條件) [第一步怎麼走，怎麼出發的]

有幾個情況是初始條件，或稱為遞迴的終止條件。

當點座標為(0, 0)起點時，顯然，方法只有一種

DP(0, 0) = 1

另外，​當座標超出板子的邊界，落在界外，方法數只有零種

DP[x, y] = 0, if x, y 在界外

同理，當座標上有障礙物時，無法通過，方法數也只有零種

DP[x, y] = 0, if x, y 上有障礙物

到這裡，已經填滿解題框架的所有內容，接著我們把它轉成程式碼，

這裡以Python作為示範

Top down 2D DP程式碼:

class Solution:
　def uniquePathsWithObstacles(self, obstacleGrid):
　　
　　can_walk = lambda x, y: (1 - obstacleGrid[y][x] )
　　
　　# height and width of matrix
　　h, w = len(obstacleGrid), len(obstacleGrid[0])
　　
　　# DP table
　　dp = {}

　　def walk(x, y):
　　　
　　　if (x, y) in dp:
　　　　# look-up DP table
　　　　return dp[x, y]

　　　if not 0 <= x < w or not 0 <= y < h or not can_walk(x, y) :
　　　　# out-of-board, or cannot walk through
　　　　dp[x, y] = 0
　　　　return 0

　　　if (x, y) == (0, 0):
　　　　# Starting point, aka base case
　　　　dp[x, y] = 1
　　　　return 1

　　　# General cases
　　　dp[x, y] = walk(x-1, y) + walk(x, y-1)
　　　return dp[(x, y)]

　　# -------------------------------------
　　return walk(w-1, h-1)

時間複雜度:

O( m * n )，板子上的每個格子點都拜訪一次。

空間複雜度:

O( m * n )，板子上總共有O(m * n)個格子點，也是DP table的大小。

Bottom up 2D DP + Space optimization 空間優化 程式碼:

class Solution:
　def uniquePathsWithObstacles(self, obstacleGrid):
　　
　　allow_to_visit = lambda x, y: (1 - obstacleGrid[y][x] )
　　
　　# height and width of matrix
　　h, w = len(obstacleGrid), len(obstacleGrid[0])
　　
　　if h * w == 0 or not allow_to_visit(0, 0):
　　　
　　　# Quick response for invalid cases
　　　return 0
　　
　　
　　# update [0][0] as start point with one valid path
　　obstacleGrid[0][0] = 1
　　
　　## base case: leftmost column
　　for y in range(1, h):
　　　obstacleGrid[y][0] = obstacleGrid[y-1][0] * allow_to_visit(0, y)
　　
　　
　　## base case: top row
　　for x in range(1, w):
　　　obstacleGrid[0][x] = obstacleGrid[0][x-1] * allow_to_visit(x, 0)
　　
　　
　　## general cases
　　for y in range(1, h):
　　　for x in range(1, w):
　　　　
　　　　# update path count from left and top
　　　　obstacleGrid[y][x] = (obstacleGrid[y][x-1] + obstacleGrid[y-1][x]) * allow_to_visit(x, y)
　　
　　return obstacleGrid[h-1][w-1]

時間複雜度:

O( m * n )，板子上的每個格子點都拜訪一次。

空間複雜度:

O( 1 )，已經使用空間優化，in-place update，沒有建立額外的2D DP Table。

學完這題之後，吸收沉澱一下，記得和系列題的第一題 Unique Path 做一個對照，背後的2D DP 演算法建構 和 Path Count 路徑計算的模型，都是高度相似的。

Reference:

[1] Python/Go O(mn) by DP [w/ Hint] - Unique Paths II - LeetCode