LeetCode 120 三角形最小路徑和：動態規劃 O(n) 空間優化解法

題目大意

給定一個三角形數組，從頂點到底邊尋找一條路徑，使路徑上數字之和最小。每步只能移動到下一行相鄰的兩個數字之一。要求空間複雜度 O(n)，n 為三角形高度。

範例

輸入: [[2],[3,4],[6,5,7],[4,1,8,3]]
輸出: 11 (路徑: 2→3→5→1)

動態規劃思路

自底向上推導：

• dp[j] 表示從底層到當前行第 j 個元素的最小路徑和
• 初始化 dp 為最後一行數值
• 從倒數第二行向上遞推：dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
• 最終 dp[0] 即為答案

Python 實現

class Solution:
    def minimumTotal(self, triangle):
        n = len(triangle)
        dp = triangle[-1][:]  # 複製最後一行
        for i in range(n-2, -1, -1):
            for j in range(i+1):
                dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
        return dp[0]

關鍵點總結

1. 原地更新 dp 數組，空間複雜度 O(n)
2. 自底向上遞推避免遞歸開銷
3. 利用相鄰關係：第 i 行第 j 個元素只能來自第 i+1 行的 j 或 j+1

複雜度

時間 O(n²)，空間 O(n)，完美符合題目要求。