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

閱讀時間約 13 分鐘

這篇文章,會帶著大家複習以前學過的格子點DP框架

並且以最小成本的下降路徑的應用題與概念為核心,

貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。


最小成本下降路徑的形式

每個格子點的值代表經過的成本。

要求從最上面那排往下方走,落到最下一排的最小成本的下降路徑


最小成本的下降路徑 I Minimum Falling Path Sum - LeetCode


這題下降路徑的規則是:

往下一排的時候,只能往左下、正下、右下的格子點

raw-image

上圖這個範例中,下墜路徑的最小成本是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)不能相同

raw-image

上圖這個範例中,下墜路徑的最小成本是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框架,還有相關的最小成本的下降路徑應用題與演算法建造,


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

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


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

avatar-img
90會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
這篇文章,會帶著大家複習以前學過的數列DP框架, 並且以費式數列、爬樓梯、骨牌拚接的應用與遞迴數列概念為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 數列DP與遞迴數列常見的形式 如果是遞迴數列,常常看到以函數型式表達
這篇文章,會帶著大家複習以前學過的二進位DP框架, 並且以0~N的整數有幾個bit1,有幾個bit0的概念為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 常見的考法 請問整數k有幾個bit1? 有幾個bit0? 請問整數0到整數N分別各有幾個bit1? 有幾個
這篇文章,會帶著大家複習以前學過的DFS框架 結合樹型DP, 並且以路徑和Path Sum的概念與應用為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 DFS 深度優先搜索框架 def dfs( parameter ): if base case or sto
這篇文章,會帶著大家複習以前學過的前綴和框架, 並且以區間和的概念與應用為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 前綴和 prefix sum框架 與 區間和計算的關係式 接下來,我們會用這個上面這種框架,貫穿一些同類型,有關聯的題目 (請讀者、或觀眾
這篇文章,會帶著大家複習以前學過的FSM+DP框架, 並且以有限狀態機 + DP狀態轉移的概念為核心, 貫穿一些相關聯最佳股票買賣系列的題目, 透過框架複現來幫助讀者理解這個實用的演算法框架。 基本的FSM + DP 框架,配合交易邏輯。 針對每一天,其實歸根究柢只有兩種狀態。 第一種
最近會試著寫一些統整類的文章, 幫助讀者、觀眾整理、吸收、複習已經學習到的演算法框架。 找零錢框架 在以前學過的題目中,我們已經學會了考零錢的抽象思考邏輯與框架,就是試著用每一種銅板去湊出n元(也就是找零錢的過程) 寫成虛擬碼或演算法,找零錢用了幾枚銅板可以這樣表達 # 銅板數目累加​
這篇文章,會帶著大家複習以前學過的數列DP框架, 並且以費式數列、爬樓梯、骨牌拚接的應用與遞迴數列概念為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 數列DP與遞迴數列常見的形式 如果是遞迴數列,常常看到以函數型式表達
這篇文章,會帶著大家複習以前學過的二進位DP框架, 並且以0~N的整數有幾個bit1,有幾個bit0的概念為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 常見的考法 請問整數k有幾個bit1? 有幾個bit0? 請問整數0到整數N分別各有幾個bit1? 有幾個
這篇文章,會帶著大家複習以前學過的DFS框架 結合樹型DP, 並且以路徑和Path Sum的概念與應用為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 DFS 深度優先搜索框架 def dfs( parameter ): if base case or sto
這篇文章,會帶著大家複習以前學過的前綴和框架, 並且以區間和的概念與應用為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 前綴和 prefix sum框架 與 區間和計算的關係式 接下來,我們會用這個上面這種框架,貫穿一些同類型,有關聯的題目 (請讀者、或觀眾
這篇文章,會帶著大家複習以前學過的FSM+DP框架, 並且以有限狀態機 + DP狀態轉移的概念為核心, 貫穿一些相關聯最佳股票買賣系列的題目, 透過框架複現來幫助讀者理解這個實用的演算法框架。 基本的FSM + DP 框架,配合交易邏輯。 針對每一天,其實歸根究柢只有兩種狀態。 第一種
最近會試著寫一些統整類的文章, 幫助讀者、觀眾整理、吸收、複習已經學習到的演算法框架。 找零錢框架 在以前學過的題目中,我們已經學會了考零錢的抽象思考邏輯與框架,就是試著用每一種銅板去湊出n元(也就是找零錢的過程) 寫成虛擬碼或演算法,找零錢用了幾枚銅板可以這樣表達 # 銅板數目累加​
你可能也想看
Google News 追蹤
Thumbnail
這是張老師的第三本書,我想前二本應該也有很多朋友們都有讀過,我想絕對是受益良多,而這次在書名上就直接點出,著重在從投資的角度來切入
Thumbnail
連載 戰國縱橫門派:鬼谷稗闔 -- 蘇秦篇 : 全球各地的華人在追本溯源的文化底蘊中只能透過春秋戰國的百家思想遠遠的觀望人生所追求的答案,找尋失落已久的獨立自主意識和自由思想。但認清自己真實的一面是不容易的,能看明白世間一切問題的解決能力更不容易。
Thumbnail
【記者:劉效益/ 報導】 北美洲台灣商會聯合總會青商部現任會長林維洋於1月15日攜手中華藝術文化交流推廣協會理事長林蘭芷於台北大直萬豪酒店主辦2024台美青商年度大會暨國際論壇,邀請全球頂尖企業專家,深化國際合作與交流。這是北美洲台灣商會聯合總會在2024年第一次在台灣舉辦理監事會議。 與會貴
Thumbnail
2023年4月5日至8日,❙法國❙ 總統 ❙馬克龍❙ 對 ❙中華人民共和國❙ 進行國事訪問,期間有關應該避免陷入 ❙中美❙ 在 ❙台灣❙ 問題上的對抗的言論在西方政界引起軒然大波。 準確地說,❙馬克龍❙ 的 ❙歐洲❙「戰略自主」論調並非在國事訪問期間發表的,而是在國事訪問後,在飛回 —— 途經廣州
Thumbnail
話說商鞅被車裂後,秦惠王恨他歸恨他,但卻很理智,商鞅的一系列方針政策繼續沿用。 因為他發現商鞅打造的這臺國家機器太好用了,短短二十年的時間,秦國從被看不起的西戎小國到被周天子官方封為西部大總管,這種感覺太美妙了。 一碼歸一碼的處理方法,顯示出了秦惠王的政治水平。 政治,是一種需要極高理性的遊戲,還是
Thumbnail
回家後當然先依照老闆娘建議冷藏一段時間,再取出食用,這篇先跟大家分享「阿華涼糕」包有內餡的綜合口味,實際品嚐後,口感真的十分軟嫩,芋頭、綠豆、紅豆、花豆、黑糖、檸檬與蓮子都是真材實料,內餡軟實外圍的涼糕Q彈,一整個好滋味。
Thumbnail
時隔多年,看到網飛(Netflix)將這部電影購入旗下著實是一種驚喜! 一個外貌看似九歲其實實際年齡早已三十有餘的偽蘿莉處心積慮機關算盡搶奪當家女主人大位的奮鬥史(無誤),我先把孤兒怨劇情的主體告訴各位,因為這部片的梗其實不難猜而且也不新鮮,比較讓我覺得有趣的是孤兒怨除了有鮮血、屍體、嚇人橋段之外,
Thumbnail
聯合國機構「政府間氣候變遷問題小組」(IPCC)本週公布了《氣候變遷報告》,是繼 2014 年以來「第一份與氣候變遷相關的科學評估」,指出全球升溫的速度快於預期,並且幾乎都是人類活動所致。工作小組呼籲,全球暖化已經「亮起紅燈」,但人們還可以避免氣候災難,只要人們立即採取積極氣候行動、終止化石燃料,
Thumbnail
歷史記載,所謂「合縱」又稱「合從」也就是聯合幾個較弱的國家對抗強大的秦國,巧合的是 alliance ㄧ字竟然也可能「alliance = a.ll.i.an.ce = 合.人人.以.anti.cina = 合.从.以.反.秦 = 合.從.以.反.秦 = 合從以反秦 = 合縱以反秦」或 ......
Thumbnail
這是張老師的第三本書,我想前二本應該也有很多朋友們都有讀過,我想絕對是受益良多,而這次在書名上就直接點出,著重在從投資的角度來切入
Thumbnail
連載 戰國縱橫門派:鬼谷稗闔 -- 蘇秦篇 : 全球各地的華人在追本溯源的文化底蘊中只能透過春秋戰國的百家思想遠遠的觀望人生所追求的答案,找尋失落已久的獨立自主意識和自由思想。但認清自己真實的一面是不容易的,能看明白世間一切問題的解決能力更不容易。
Thumbnail
【記者:劉效益/ 報導】 北美洲台灣商會聯合總會青商部現任會長林維洋於1月15日攜手中華藝術文化交流推廣協會理事長林蘭芷於台北大直萬豪酒店主辦2024台美青商年度大會暨國際論壇,邀請全球頂尖企業專家,深化國際合作與交流。這是北美洲台灣商會聯合總會在2024年第一次在台灣舉辦理監事會議。 與會貴
Thumbnail
2023年4月5日至8日,❙法國❙ 總統 ❙馬克龍❙ 對 ❙中華人民共和國❙ 進行國事訪問,期間有關應該避免陷入 ❙中美❙ 在 ❙台灣❙ 問題上的對抗的言論在西方政界引起軒然大波。 準確地說,❙馬克龍❙ 的 ❙歐洲❙「戰略自主」論調並非在國事訪問期間發表的,而是在國事訪問後,在飛回 —— 途經廣州
Thumbnail
話說商鞅被車裂後,秦惠王恨他歸恨他,但卻很理智,商鞅的一系列方針政策繼續沿用。 因為他發現商鞅打造的這臺國家機器太好用了,短短二十年的時間,秦國從被看不起的西戎小國到被周天子官方封為西部大總管,這種感覺太美妙了。 一碼歸一碼的處理方法,顯示出了秦惠王的政治水平。 政治,是一種需要極高理性的遊戲,還是
Thumbnail
回家後當然先依照老闆娘建議冷藏一段時間,再取出食用,這篇先跟大家分享「阿華涼糕」包有內餡的綜合口味,實際品嚐後,口感真的十分軟嫩,芋頭、綠豆、紅豆、花豆、黑糖、檸檬與蓮子都是真材實料,內餡軟實外圍的涼糕Q彈,一整個好滋味。
Thumbnail
時隔多年,看到網飛(Netflix)將這部電影購入旗下著實是一種驚喜! 一個外貌看似九歲其實實際年齡早已三十有餘的偽蘿莉處心積慮機關算盡搶奪當家女主人大位的奮鬥史(無誤),我先把孤兒怨劇情的主體告訴各位,因為這部片的梗其實不難猜而且也不新鮮,比較讓我覺得有趣的是孤兒怨除了有鮮血、屍體、嚇人橋段之外,
Thumbnail
聯合國機構「政府間氣候變遷問題小組」(IPCC)本週公布了《氣候變遷報告》,是繼 2014 年以來「第一份與氣候變遷相關的科學評估」,指出全球升溫的速度快於預期,並且幾乎都是人類活動所致。工作小組呼籲,全球暖化已經「亮起紅燈」,但人們還可以避免氣候災難,只要人們立即採取積極氣候行動、終止化石燃料,
Thumbnail
歷史記載,所謂「合縱」又稱「合從」也就是聯合幾個較弱的國家對抗強大的秦國,巧合的是 alliance ㄧ字竟然也可能「alliance = a.ll.i.an.ce = 合.人人.以.anti.cina = 合.从.以.反.秦 = 合.從.以.反.秦 = 合從以反秦 = 合縱以反秦」或 ......