1 題目描述

給定一個三角形，找到從頂部到底部的最小路徑和。每一步只能移動到下一行的相鄰元素上。

2 解法

其實這題與leetcode #300 Longest Increasing Subsequence有點類似，如果我們嘗試用樹狀圖，把所有可能寫出來，如果今天題目是[[1], [2,3], [4,5,6], [7,8,9,10]]大概會長以下這樣：

特徵如下：

從底部慢慢往上走，算出每層由下往上的最佳解
dp 的值是由下往上的最佳解

2.1 Recursion

但我們先慢慢來吧，先寫出Recursion的寫法。他的問題也是經典的拿與不拿問題。題目可以看到，如果我這一層layer取i，那我下一層layer只能取i或是i+1，這兩個選最小的。

其實Recursive的關係式
(helper是recursive的function)

1	min(helper(layer+1, i), helper(layer+1, i+1)) + triangle[layer][i]

那最小問題基本上就是當已經走到底了，直接回傳triangle[layer][i]，因為這時候就是最底層了，不用再往下走了。

1
2
3

# index 從 0 開始記得 -1 
if layer == len(triangle) - 1:
    return triangle[layer][i]

完整程式碼

def minimumTotal(self, triangle: List[List[int]]) -> int:
    def helper(layer: int, idx: int) -> int:
        # 最小問題
        if layer == len(triangle)-1:
            return triangle[layer][idx]
        # 關係式
        return triangle[layer][idx] + min(helper(layer+1, idx), helper(layer+1, idx+1))
    
    # 最後回傳從底部累加到頂部的最小值
    return helper(0,0)

2.2 Recursion + Memoization

接下來我們就是要加上Memoization，這樣就不用一直重複計算了。這裡我們可以用一個dp的list來記錄已經計算過的值，我們可以先建立一個與triangle一樣大小的list，然後每次計算過的值就存進去，下次再遇到就直接回傳。

建立一個dp[layer][idx]是當前的從底部走上去的最佳解

1	dp = [[0 for _ in range(len(triangle[i]))] for i in range(len(triangle))]

當發現dp不是0時，直接回傳

1 2	if dp[layer][idx] != 0: return dp[layer][idx]

完整程式碼

~def minimumTotal2(self, triangle: List[List[int]]) -> int:
    def helper(layer: int, idx: int) -> int:
        # 如果已經計算過，直接回傳
        if dp[layer][idx] != 0:
            return dp[layer][idx]
        
        # 最小問題
        if layer == len(triangle)-1:
            dp[layer][idx] = triangle[layer][idx]
            return dp[layer][idx]

        # 關係式
        dp[layer][idx] = triangle[layer][idx] + min(helper(layer+1, idx), helper(layer+1, idx+1))

        return dp[layer][idx]

    dp = [[0 for _ in range(len(triangle[i]))] for i in range(len(triangle))]
    return helper(0,0)

2.3 Iterative + Tabulation

既然從底部走上去，我們可以從底部開始往上走，這樣就不用一直遞迴了。我們可以從倒數第二層開始，然後往上走，每一層都是取最小的值加上自己，這樣就可以得到最後的答案。

def minimumTotal3(self, triangle: List[List[int]]) -> int:
    dp = [[0 for _ in range(len(triangle[i]))] for i in range(len(triangle))]

    # 從底部往上走
    for layer in range(len(triangle)-1, -1, -1):
        # 每一層的每一個值
        for idx in range(len(triangle[layer])):
            # 最小問題 先把底部的值存進去 dp 
            if layer == len(triangle)-1:
                dp[layer][idx] = triangle[layer][idx]
            else:
                dp[layer][idx] = triangle[layer][idx] + min(dp[layer+1][idx], dp[layer+1][idx+1])

    return dp[0][0]

2.4 Iterative + Tabulation (Space Optimized)

其實我們可以發現，我們每次只會用到下一層的值，所以我們可以只用一個list來存下一層的值，這樣就可以省下空間。

def minimumTotal4(self, triangle: List[List[int]]) -> int:
    # dp 只建立最長的那一層數量
    dp = [0 for _ in range(len(triangle[-1]))]

    for layer in range(len(triangle)-1, -1, -1):
        for idx in range(len(triangle[layer])):
            if layer == len(triangle)-1:
                dp[idx] = triangle[layer][idx]
            else:
                dp[idx] = triangle[layer][idx] + min(dp[idx], dp[idx+1])

    return dp[0]

其實還有更扯的，不需要建立dp，直接用triangle就可以了，因為我們每次都會更新triangle的值，所以不用另外建立一個list。
雖然他會改動到原本的triangle，但是到最後整個triangle的值就是從底部走上去的最佳解。

def minimumTotal5(self, dp: List[List[int]]) -> int:
    n = len(dp)

    for i in range(n - 2, -1, -1):
        for j in range(len(dp[i])):
            dp[i][j] += min(dp[i + 1][j], dp[i + 1][j + 1])

    return dp[0][0]