用格子點DP來解 三角形最小成本下降路徑 Triangle_Leetcode #120

Moritz Mentges on Unsplash

題目敘述 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

[1] Triangle - LeetCode

回到DP特訓班目錄 和 學習路徑