題目描述

給定三角形數組，從頂部到底部相鄰路徑最小和。例：

[ [2], [3,4], [6,5,7], [4,1,8,3] ]

最小路徑：2→3→5→1 = 11。進階要求 O(n) 額外空間（n 為行數）。

動態規劃：自底向上 / 自頂向下

設 f(i,k) 為從頂到第 i 行第 k 個頂點的最小路徑和。轉移：

f(i,k) = min(f(i-1,k-1), f(i-1,k)) + triangle[i][k]

邊界：每行首尾元素只有一個上層鄰居。

O(n) 空間優化：原地修改 / 一維數組

自底向上：從倒數第二行開始，每行元素加上下層相鄰兩值的較小者。最終頂點即答案。或用一維 dp 數組滾動更新。

代碼實現

class Solution {
public:
    int minimumTotal(vector>& triangle) {
        int n = triangle.size();
        if (n == 0) return 0;
        // 自底向上原地修改
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
            }
        }
        return triangle[0][0];
    }
};

或不修改輸入，用一維數組：

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];
}

完整版（含邊界處理的自頂向下）

class Solution {
public:
    int minimumTotal(vector>& triangle) {
        int n = triangle.size();
        if (n == 0) return 0;
        for (int i = 1; i < n; i++) {
            int m = triangle[i].size();
            for (int j = 0; j < m; j++) {
                if (j == 0) triangle[i][j] += triangle[i-1][j];
                else if (j == m-1) triangle[i][j] += triangle[i-1][j-1];
                else triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j]);
            }
        }
        int res = triangle[n-1][0];
        for (int i = 1; i < triangle[n-1].size(); i++)
            res = min(res, triangle[n-1][i]);
        return res;
    }
};

複雜度

• 時間：O(n²) 遍歷所有元素
• 空間：O(1) 原地修改 / O(n) 一維數組