合縱連橫: 從 移動路徑 理解 格子點DP 框架的本質。
這篇文章，會帶著大家複習以前學過的格子點DP框架，
並且以移動路徑Unique Path的概念與應用為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
格子點DP框架
依循題目的定義和規則，找出格子點移動的共同模式。
以本篇文章的例題為例，每一步可以選擇往右走一個或往下走一格。
因此，反過來說，抵達格子點(x, y)的方式有兩種:
1.可以從上面(x, y-1)走過來。
2.可以從左邊(x-1, y)走過來。
示意圖
接下來，我們會用這個上面這種框架，貫穿一些同類型，有關聯的題目
(請讀者、或觀眾留意上面的這種 前綴和 框架，之後的解說會反覆出現)
Unique Paths - LeetCode 路徑總數
題目給定一個已知大小的矩陣，起點固定在左上角，終點固定在右下角。
每次移動時，可以向右走一格，或向下走一格。
要求我們計算從起點到終點的路徑總數有多少。
這題剛好以前有路過教學影片，提供給讀者作為參考。
狀態轉移關係式:
從剛剛的示意圖圖可以知道:
抵達格子點(x, y)有兩種方式，一種是從上面走過來，另一種是從左邊走過來。
因此，抵達格子點(x, y)的路徑總數
= 抵達格子點(x, y-1)的路徑總數 + 抵達格子點(x-1, y)的路徑總數
= DP[x, y-1] + DP[x-1, y]
初始條件:
起點，最上面那排，和最左邊那排都只有一種抵達方式。
DP[0, y] = 1
DP[x, 0] = 1
以Top-down DP的演算法來寫解題程式碼:
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# key: x, y
# value: path count of x, y
memo = {}
def dp(x, y):
# Look-up table
if (x, y) in memo:
return memo[(x,y)]
# Base case
if x == 0 or y == 0:
memo[(x,y)] = 1
return 1
# General cases: each grid can reach from left step left, or one step up
memo[(x,y)] = dp(x-1, y ) + dp(x, y-1)
return memo[(x,y)]
return dp(x=n-1, y=m-1)
很基本的暖身題，依樣畫葫蘆即可!
Unique Paths II - LeetCode 路徑總數II 途中可能有障礙物
這題其實也很類似，只是多了一個小變化，途中可能會有障礙物(地圖中會標記為1)，
無法通過。
但是，移動的規則還是相同，每次移動時，可以向右走一格，或向下走一格。
那麼，我們只要在計算的時候，額外判斷現在這個格子點有沒有障礙物，
如果有障礙物，直接返回0即可。(因為有障礙物不能走)
以Top-down 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 = {}
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)]
稍有變化，但是思考邏輯相似。
Minimum Path Sum - LeetCode 從起點走到終點的最小成本
這題也是很類似，這次途中沒有障礙物。
但是改要求我們計算從起點移動到終點的最小成本。
移動的規則還是相同，每次移動時，可以向右走一格，或向下走一格。
當走到點格子(x, y)時，需要付出grid[y][x]的成本。
註: 這邊陣列座標顛倒，是因為陣列是以row-major方式存取下標。
狀態轉移關係式:
從剛剛的示意圖圖可以知道:
抵達格子點(x, y)有兩種方式，一種是從上面走過來，另一種是從左邊走過來。
因此，抵達格子點(x, y)的最小成本
DP[x, y]
= 格子點(x, y) 的成本 + 從前面走過來的最小成本
= grid[y][x] + min( DP[x, y-1] + DP[x-1, y] )
示意圖
image
初始條件:
起點(0, 0)的成本
= DP[0,0 ]
= grid[0][0]
以Top-down DP的演算法來寫解題程式碼:
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
# height and width of board
h, w = len(grid), len(grid[0])
## dictionary
# key: coordination
# value: minial cost from (0,0) to (x, y)
minCostTable = { (0,0) : grid[0][0] }
def dp(x, y):
# look-up table
if (x, y) in minCostTable:
return minCostTable[(x,y)]
# base case: top row
if x > 0 and y == 0:
minCostTable[(x,y)] = grid[y][x] + dp(x-1, y)
# base case: left-most column
elif y > 0 and x == 0:
minCostTable[(x,y)] = grid[y][x] + dp(x, y-1)
# general cases:
else:
minCostTable[(x,y)] = grid[y][x] + min( dp(x, y-1), dp(x-1, y) )
return minCostTable[(x,y)]
# =================================
return dp(w-1, h-1)
改為計算從起點到終點的最小移動成本，但是基本思想還是類似。
結語
好，今天一口氣介紹了最精華的部分，
通用的格子點DP框架，還有相關的移動路徑應用題與演算法建造，
希望能幫助讀者、觀眾徹底理解它的原理，
並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！
感謝收看囉! 我們下篇文章再見~
