LeetCode Triangle：三角矩陣最小路徑和（DP O(n) 空間）

問題描述

給定三角形數組，從頂部到底部，每步只能移動到下一行相鄰數字，求最小路徑和。例：[[2],[3,4],[6,5,7],[4,1,8,3]] → 2+3+5+1=11。

DP 狀態與轉移

自底向上：dp[j] 表示從第 i 行第 j 個元素到底部的最小和。初始 dp = 最後一行。向上更新：dp[j] = triangle[i][j] + min(dp[j], dp[j+1])。最終 dp[0] 即答案。

代碼實現 (O(n) 空間)

int minimumTotal(vector>& triangle) {
    int n = triangle.size();
    vector dp = triangle.back();
    for (int i = n-2; i >= 0; --i) {
        for (int j = 0; j <= i; ++j)
            dp[j] = triangle[i][j] + min(dp[j], dp[j+1]);
    }
    return dp[0];
}

自頂向下寫法（同樣 O(n) 空間）

vector dp(n, INT_MAX);
dp[0] = triangle[0][0];
for (int i = 1; i < n; ++i) {
    for (int j = i; j >= 0; --j) {
        dp[j] = triangle[i][j] + min(dp[j], j>0?dp[j-1]:INT_MAX);
    }
}
return *min_element(dp.begin(), dp.end());

關鍵點

• 原地修改輸入數組可達 O(1) 額外空間（若允許修改輸入）。
• 自底向上邏輯更簡潔，無需處理邊界 INF。
• 時間 O(n²)，n 為行數。