120. Triangle

Medium

Description

給定一個三角形陣列 triangle，找出從頂部到底部的最小路徑總和。每一步只能移動到下一行的相鄰節點（即索引 i 或 i+1）。

Example:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] Output: 11

Intuition#

從底部往上 DP，每個位置選擇下一行左右鄰居中較小的加上自己。

自頂向下會需要處理邊界，自底向上更簡潔
dp[j] 代表從底部到當前行第 j 個位置的最小路徑和
狀態轉移：dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
可以直接用一維陣列滾動更新

Approaches#

1: Top-Down Memoization#

概念: 從頂部遞迴向下，記憶化每個 (row, col) 的最小路徑和
時間複雜度: O(n^2)
空間複雜度: O(n^2)

class Solution {
    fun minimumTotal(triangle: List<List<Int>>): Int {
        val n = triangle.size
        val memo = Array(n) { IntArray(it + 1) { Int.MAX_VALUE } }
        fun dp(row: Int, col: Int): Int {
            if (row == n) return 0
            if (memo[row][col] != Int.MAX_VALUE) return memo[row][col]
            memo[row][col] = triangle[row][col] + minOf(dp(row + 1, col), dp(row + 1, col + 1))
            return memo[row][col]
        }
        return dp(0, 0)
    }
}

⭐2: Bottom-Up with O(n) Space#

概念: 從最底行往上逐行合併，只用一維陣列記錄當前行的最小路徑和
時間複雜度: O(n^2)
空間複雜度: O(n)

class Solution {
    fun minimumTotal(triangle: List<List<Int>>): Int {
        val n = triangle.size
        val dp = triangle[n - 1].toIntArray()
        for (i in n - 2 downTo 0) {
            for (j in 0..i) {
                dp[j] = triangle[i][j] + minOf(dp[j], dp[j + 1])
            }
        }
        return dp[0]
    }
}

🔑 Takeaways#

Pattern: 自底向上 DP — 反向思考可以簡化邊界處理
關鍵技巧: 從底部往上更新時，dp[j+1] 尚未被覆蓋，因此可以安全地用一維陣列滾動