LeetCode 120 Triangle：自底向上動態規劃

這是一道經典的動態規劃題，給定一個三角形數組，從頂點到底邊尋找路徑和最小值。採用自底向上的思路，直接在原數組上修改，最後 triangle[0][0] 即為答案。

狀態轉移方程

triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1])

從倒數第二行開始向上迭代，每層每個節點取其下層相鄰兩節點的較小值累加。

代碼實現

class Solution {
public:
    int minimumTotal(vector<vector<int>> &triangle) {
        for (int i = triangle.size() - 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];
    }
};

相關題目延伸

• HDU 2084 數塔：本質相同，自底向上求最大路徑和。
• HDU 1176 免費餡餅：進階版，可視為矩陣路徑問題，狀態轉移方程為 dp[i][j] = max(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]) + pie[i][j]。

掌握自底向上 DP 思想，此類三角形/矩陣路徑問題皆可迎刃而解。