合縱連橫: 從 格子點DP框架 理解 最小成本的下降路徑

Yomex Owo on Unsplash

這篇文章，會帶著大家複習以前學過的格子點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框架，還有相關的最小成本的下降路徑應用題與演算法建造，

希望能幫助讀者、觀眾徹底理解它的原理，

並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！

感謝收看囉! 我們下篇文章再見~