用格子點DP來解 三角形最小成本下降路徑 Triangle_Leetcode #120
題目敘述 Triangle
題目會給我們一個三角形的二維陣列triangle ，每個元素分別代表每個格子的成本，請問我們從最頂端到底部的下墜路徑的最小成本總和是多少?
每次下墜到下一排的時候，可以有兩種選擇:
1.往左下方的格子點移動。
2.往右下方的格子點移動。
測試範例
Example 1:
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
2
3 4
6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).
最小成本的下降路徑為: 2 -> 3 -> 5 -> 1
Example 2:
Input: triangle = [[-10]]
Output: -10
約束條件
Constraints:
1 <= triangle.length <= 200
三角形陣列的長度介於1~200之間。
triangle[0].length == 1
三角形陣列的頂端只會有一個元素。
triangle[i].length == triangle[i - 1].length + 1
下一排的長度 = 前一排的長度+1
-10^4 <= triangle[i][j] <= 10^4
每個陣列元素值介於 負一萬~正一萬 之間。
進階提問
Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?
能不能想到一個只使用O(n)線性空間的演算法?
觀察 下墜規則
每次下墜到下一排的時候，可以有兩種選擇:
1.往左下方的格子點移動。
2.往右下方的格子點移動。
換句話說，當我們位在[row][col]這個格子點的時候，可以怎麼過來?
1.從左上方的格子點[row-1][col-1]掉下來
2.從右上方的格子點[row-1][col]掉下來
我們可以定義DP[row, col]代表從頂端下落到[row][col]的最小路徑成本
那麼，根據下墜規則，可以知道
DP[row, col]
=下落到[row][col]的最小路徑成本
=[row][col]自己的成本 + min{ 落到左上方格子點, 落到右上方格子點}
= triangle[row][col] + min{ DP[row-1][col-1], DP[row-1][col] }
什麼時候停下來?
當回溯到最頂端的格子點的時候，也就是起點，可以停下來。
DP[row, col] = triangle[0][0] if (row, col) = (0, 0)
演算法 DP動態規劃
1.定義DP狀態
承接觀察點的思考，定義DP[row, col]代表從頂端下落到[row][col]的最小路徑成本。
題目所求是從頂點落到最下層的最小路徑成本。
題目所求 = min{ DP[row, col] where row == 最後一層的層數}
2.推導DP狀態轉移關係式
當我們位在[row][col]這個格子點的時候，可以怎麼過來?
1.從左上方的格子點[row-1][col-1]掉下來
2.從右上方的格子點[row-1][col]掉下來
那麼，根據下墜規則，可以知道
DP[row, col]
=下落到[row][col]的最小路徑成本
=[row][col]自己的成本 + min{ 落到左上方格子點, 落到右上方格子點}
= triangle[row][col] + min{ DP[row-1][col-1], DP[row-1][col] }
3.釐清DP初始狀態
什麼時候是最小規模的問題?
什麼時候往上回溯的過程可以停下來?
當回溯到最頂端的格子點的時候，也就是起點，可以停下來。
DP[row, col] = triangle[0][0] if (row, col) = (0, 0)
程式碼 DP動態規劃
# O(n^2) aux space
# O(n^2) time
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
INF = math.inf
# height of triangle
h = len(triangle)
dp = {}
def fall( row, col ):
if (row, col) in dp:
return dp[row, col]
if row == 0 and col == 0:
## Base case, top most element
dp[row, col] = triangle[0][0]
return triangle[0][0]
elif col < 0 or col > row:
## Base case, return infinity on out-of-boundary
dp[row, col] = INF
return INF
dp[row, col] = triangle[row][col] + min( fall(row-1, col-1), fall(row-1, col) )
return dp[row, col]
# ------------------------------------
# backtrack from bottom row to compute minimal cost of falling path
return min( fall(h-1, col) for col in range(h) )
複雜度分析
時間複雜度: O(n^2)
需要掃描過每個矩陣元素，去更新下墜路徑的最小成本，所需時間為O(n^2)。
空間複雜度: O(n^2)
DP table需要紀錄每個格子點的最小下墜路徑成本，所需空間為O(n^2)。
更進一步觀察，可以發現每一排只需要上一排的資訊。
也就是說，只要儲存目前 這一排 和 前一排 即可滿足計算最小成本的需求。
程式碼 DP動態規劃 空間優化
# O(n) aux space, optimization in space
# O(n^2) time
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
## DP Table
# Key: row
# Value: minimal falling cost
dp = {}
def downfall(row):
## Look-up DP table
if row % 2 in dp:
return dp[row%2]
## Base case
if row == 0:
dp[row] = triangle[[0][0]]
return triangle[[0][0]]
## General case:
prevRow = downfall(row-1)
head = triangle[row][0] + prevRow[0]
curRow = []
for col in range(1, row):
curRow.append( triangle[row][col] + min(prevRow[col], prevRow[col-1]) )
tail = triangle[row][row] + prevRow[-1]
dp[ row%2 ] = [head] + curRow + [tail]
return dp[ row%2 ]
# ---------------------------------
return min( downfall( row= len(triangle)-1 ) )
複雜度分析
時間複雜度: O(n^2)
需要掃描過每個矩陣元素，去更新下墜路徑的最小成本，所需時間為O(n^2)。
空間複雜度: O(n)
DP table需要紀錄兩排格子點的最小下墜路徑成本，所需空間為O(2n)=O(n)。
再更進一步，發現其實計算順序都是從上往下，從左到右，爾且更新後不會回頭更改。
因此可以直接拿掉DP table，直接in-place update在triangle陣列即可。
# O(n) aux space, optimization in space
# O(n^2) time
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
def downfall(row):
## Base case
if row == len(triangle):
# Already reach final level
return
## General case:
triangle[row][0] += triangle[row-1][0]
for col in range(1, row):
triangle[row][col] += min(triangle[row-1][col], triangle[row-1][col-1])
triangle[row][row] += triangle[row-1][row-1]
# down fall to next level
downfall(row+1)
return
# ---------------------------------
downfall( row=1 )
return min( triangle[-1] )
複雜度分析
時間複雜度: O(n^2)
需要掃描過每個矩陣元素，去更新下墜路徑的最小成本，所需時間為O(n^2)。
空間複雜度: O(n)
雖然沒有DP Table，但是遞迴呼叫還是需要run-time call stack，
所需空間為O(n)=O(n)。
既然都in-place update，那遞迴也可以打開成等價的for loop迭代，
節省遞迴stack空間，這樣空間就被優化成O(1)，不需要額外的DP table和遞迴呼叫。
# O(1) aux space, optimization in space, in-place update
# O(n^2) time
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
height = len(triangle)
for row in range(1, height ):
## General case:
triangle[row][0] += triangle[row-1][0]
for col in range(1, row):
triangle[row][col] += min(triangle[row-1][col], triangle[row-1][col-1])
triangle[row][row] += triangle[row-1][row-1]
return min( triangle[height-1] )
複雜度分析
時間複雜度: O(n^2)
需要掃描過每個矩陣元素，去更新下墜路徑的最小成本，所需時間為O(n^2)。
空間複雜度: O(1)
In-place udpate，原位更新，不需要DP table，也不需要遞迴呼叫。
其他的臨時變數都是固定尺寸，所需空間為O(1)常數級別。
關鍵知識點 分析下墜規則
當我們位在[row][col]這個格子點的時候，可以怎麼過來?
1.從左上方的格子點[row-1][col-1]掉下來
2.從右上方的格子點[row-1][col]掉下來
那麼，根據下墜規則，可以知道
DP[row, col]
=下落到[row][col]的最小路徑成本
=[row][col]自己的成本 + min{ 落到左上方格子點, 落到右上方格子點}
= triangle[row][col] + min{ DP[row-1][col-1], DP[row-1][col] }
強烈建議複習高度相關的
一魚多吃 用DP解最小成本的下墜路徑和 Minimum Falling Path Sum_Leetcode #931
鞏固知識點，加深印象！
Reference
回到DP特訓班目錄 和 學習路徑
你可能也想看
