120. Triangle | LeetCode | Swift

每日一題

https://leetcode.com/problems/triangle/description/?envType=daily-question&envId=2025-09-19

日期

2025/9/25

Bottom-up DP 解法

分析題目之後，會發現這是一題 DP (Dynamic Programming) 的題目，意味著我們需要找到最小的 routine ，再重複執行 routine 取得最終結果。

Routine

自己 + 最小值（下一行[index], 下一行[index + 1]）

從底部往上開始走訪：

class Solution {
    func minimumTotal(_ triangle: [[Int]]) -> Int {
        var dp = triangle[triangle.count - 1]
        
        for i in stride(from: triangle.count - 2, through: 0, by: -1) {
            for j in 0..<triangle[i].count {
            		// Routine:
                // 直接更新 dp[j]，選擇下一行兩個可能路徑的最小值
                dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
            }
        }
        
        return dp[0]
    }
}

使用高階函式・一行解法

這個 dp 的寫法還算單純，於是試著自己用用看高階函式

參考 ChatGPT 和 iamhands0me 的解法，最後還是 iamhands0me 寫法最漂亮 ，快幫他按讚：

• https://leetcode.com/problems/triangle/solutions/7221522/swift-1-liner-0-ms-2-approaches

Swift Algorithm 的 adjacentPairs

這個函式可以幫我們把一個陣列變成兩兩一對（文件），例如：

[4, 1, 8, 3]
// 進行 adjacentPairs
// 結果： [(4, 1), (1, 8), (8, 3)]​

這時候再透過 min 就可以找出最小值：

[(4, 1), (1, 8), (8, 3)]​.map { min($0, $1) }
// 結果： [1, 1, 3]

更精簡一點就可以寫成這樣

[(4, 1), (1, 8), (8, 3)]​.map(min)
// 結果： [1, 1, 3]

程式碼

邏輯本身大同小異，比較考驗對高階函式的熟練程度。

class Solution {
    func minimumTotal(_ triangle: [[Int]]) -> Int {
        triangle
            .reversed()
            // 建立一個基底為 0 的 dummy 陣列給 bottom most row 
            .reduce(Array(repeating: 0, count: triangle.count + 1)) {
                zip(
                    $1,
                    $0.adjacentPairs().map(min)
                )
                .map(+)
            }
            .first ?? 0
    }
}