合縱連橫: 從 格子點DP框架 理解 最小成本的下降路徑
這篇文章，會帶著大家複習以前學過的格子點DP框架，
並且以最小成本的下降路徑的應用題與概念為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
最小成本下降路徑的形式
每個格子點的值代表經過的成本。
要求從最上面那排往下方走，落到最下一排的最小成本的下降路徑。
最小成本的下降路徑 I Minimum Falling Path Sum - LeetCode
這題下降路徑的規則是:
往下一排的時候，只能往左下、正下、右下的格子點。
上圖這個範例中，下墜路徑的最小成本是13
可以是 1 -> 5 -> 7 或者 1 -> 4 -> 8
反過來說，等價的說法就是:
這一排的個子點，往上回溯的時候，只有可能從 左上，正上，右上的格子點過來。
再更進一步，
如果我們定義DP[row][col]代表從最上面落到[row][col]這個格子點的最小成本，
把通則寫成虛擬碼或者演算法的形式，就是
DP[row][col]
= 落到[row][col]的最小成本
= [row][col]這個格子點的成本 + 從第一排落到上一排格子點的成本
= matrix[rol][col] + min{ 左上格子點的下降路徑成本、正上格子點的下降路徑成本、右上格子點的下降路徑成本}
=matrix[rol][col] + min{ DP[row-1][col-1]、DP[row-1][col]、DP[row-1][col+1]}
那初始條件呢?
其實初始條件就是最上排，也就是第一排的格子點，相等於起點的那一排。
DP[row][col] 當 row 等於 0的時候
=[rol][col]這個格子點自己本身的成本
=matrix[row][col]
現在DP定義、通則、初始條件都有了，寫成程式碼即可。
Top-down DP程式碼
class Solution:
def minFallingPathSum(self, matrix: List[List[int]]) -> int:
h, w = len(matrix), len(matrix[0])
INF = sys.maxsize
memo = {}
def dp(row, col):
# Look-up DP table
if (row, col) in memo:
return memo[row, col]
## Base case: top row
if row == 0 and 0 <= col < w:
memo[0,col] = matrix[0][col]
return matrix[0][col]
## Base case: out-of boundary
if col < 0 or col >= w:
memo[row,col] = INF
return INF
## General case: current cost + minimal cost of neighbor on previous row
memo[row, col] = matrix[row][col] + min( dp(row-1,col+offset) for offset in (-1, 0, 1) )
return memo[row, col]
# ------------------------------------------------
return min( dp(h-1, col) for col in range(w) )
等價的Bottom-up DP程式碼
class Solution:
def minFallingPathSum(self, matrix: List[List[int]]) -> int:
size = len(matrix)
if size == 1:
# Quick response for single row
return matrix[0][0]
# Update matrix[y][x] from second row to last row
for y in range( 1, size):
# sacn each column from 0 to size-1
for x in range( size ):
# find falling path of minimal cost with optimal substructure
min_prev = matrix[y-1][x]
if x > 0:
min_prev = min( min_prev, matrix[y-1][x-1] )
if x < size-1:
min_prev = min( min_prev, matrix[y-1][x+1] )
# update the cost of falling path, destination is [y][x], with optimal substructure
matrix[y][x] = matrix[y][x] + min_prev
# the cost of minimum falling path is the minimum value of last row
return min( matrix[size-1] )
接下來再看一個變化題。
最小成本的下降路徑 II Minimum Falling Path Sum II
這題下降路徑的規則是:
往下一排的時候，不能在同一個column，也就是x座標(column)不能相同。
上圖這個範例中，下墜路徑的最小成本是13
最佳下墜路徑是 1 -> 5 -> 7
反過來說，等價的說法就是:
這一排的個子點，往上回溯的時候，只有可能從上方x座標不同的格子點過來。
再更進一步，
如果我們定義DP[row][col]代表從最上面落到[row][col]這個格子點的最小成本，
把通則寫成虛擬碼或者演算法的形式，就是
DP[row][col]
= 落到[row][col]的最小成本
= [row][col]這個格子點的成本 + 從第一排落到上一排格子點的成本
= matrix[rol][col] + min{ 上一排x座標不同的格子點的下降路徑成本}
=matrix[rol][col] + 上一排格子點的下降路徑成本最小值
(假如正上方的格子點不是最小值)
或者
=matrix[rol][col] + 上一排格子點的下降路徑成本次小值
(假如正上方的格子點是最小值)
那初始條件呢?
其實初始條件就是最上排，也就是第一排的格子點，相等於起點的那一排。
DP[row][col] 當 row 等於 0的時候
=[rol][col]這個格子點自己本身的成本
=matrix[row][col]
現在DP定義、通則、初始條件都有了，寫成程式碼即可。
Top-down DP程式碼
class Solution:
def minFallingPathSum(self, matrix: List[List[int]]) -> int:
h = w = len(matrix)
memo = {}
smallest_2 = {}
def dp(row, col):
# Look-up DP table
if (row, col) in memo:
return memo[row, col]
## Base case: top row
if row == 0 and 0 <= col < w:
memo[row, col] = matrix[0][col]
return memo[row, col]
## General case: current cost + minimal cost of neighbor on previous row
if row-1 not in smallest_2:
smallest_2[row-1] = heapq.nsmallest(2, [dp(row-1, col) for col in range(w)])
# Cannot fall to same column
if memo[row-1,col] == smallest_2[row-1][0]:
memo[row, col] = matrix[row][col] + smallest_2[row-1][1]
else:
memo[row, col] = matrix[row][col] + smallest_2[row-1][0]
return memo[row, col]
# ------------------------------------------------
return min( dp(h-1, col) for col in range(w) )
等價的Bottom-up DP程式碼
class Solution:
def minFallingPathSum(self, arr: List[List[int]]) -> int:
h = w = len(arr)
## Base case:
# top row
if h == 1:
return arr[0][0]
## General case:
# current cost + minimal cost of neighbor on previous row
for y in range(1, h):
min_prev_candidates = heapq.nsmallest(2, arr[y - 1])
for x in range(w):
if arr[y-1][x] == min_prev_candidates[0]:
arr[y][x] = arr[y][x] + min_prev_candidates[1]
else:
arr[y][x] = arr[y][x] + min_prev_candidates[0]
return min( arr[h-1] )
結語
好，今天一口氣介紹了最精華的部分，
通用的格子點DP框架，還有相關的最小成本的下降路徑應用題與演算法建造，
希望能幫助讀者、觀眾徹底理解它的原理，
並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！
感謝收看囉! 我們下篇文章再見~
你可能也想看
