題目連結(https://leetcode.com/problems/triangle/description/?envType=daily-question&envId=2025-09-25)

今天來寫每日一題，DP+ 最短路徑問題

和以前寫過的 path sum, climbing stairs 相關

1. Repeat（題目重複確認）

• 輸入： triangle 二維 array
• 輸出：從頂端到底部最小的路徑總和
• 前提：
  • 1 <= triangle.length <= 200
  • triangle[0].length == 1
  • triangle[i].length == triangle[i - 1].length + 1
  • 104 <= triangle[i][j] <= 104

2. Examples（舉例確認理解）

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
最短路徑為 2 -> 3 -> 5 -> 1，總和為 11

3. Approach（解題思路）

方法 1：自底而上的動態規劃

• 從三角形底部開始，逐層向上計算到達每個位置的最小路徑和

• 對於每個位置 (i,j)，它的最小路徑和 = 當前值 + min(下一層相鄰兩個位置的最小路徑和)

  狀態轉移方程：dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])

• 時間複雜度：O(n^2)

• 空間複雜度：O(n^2)

方法 2：自底而上的動態規劃(空間優化)

• 計算第 i 層時，只需要第 i+1 層的信息，計算完第 i 層後，第 i+1 層的信息就不再需要，所以可以直接覆蓋！只需要一個變數來存。
• 狀態轉移方程：dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
  • dp[j] 和 dp[j+1] 都是下一層的值
  • 從左到右更新當前層更新 dp[j] 不會影響到 dp[j+1]（因為 j < j+1）
• 時間複雜度：O(n^2)
• 空間複雜度：O(n)

4. Code（C++）

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>> dp = triangle;

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

    }
};

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<int> dp(triangle[n-1]); //1-array

        for(int i = n-2; i >= 0; i--){ //from n-2 layer
            for(int j = 0; j <= i; j++){
                dp[j] = triangle[i][j] + min(dp[j], dp[j+1]); //transfer
            }
        } 
        return dp[0];
        
    }
};

5. Test 範例

• Input：triangle = [[2], [3,4], [6,5,7], [4,1,8,3]]
• n = 4
• dp 初始化：dp = [4, 1, 8, 3] (來自 triangle[3])

第一輪迴圈 (i = 2)

• j = 0: dp[0] = triangle[2][0] + min(dp[0], dp[1])
• j = 1: dp[1] = triangle[2][1] + min(dp[1], dp[2])
• j = 2: dp[2] = triangle[2][2] + min(dp[2], dp[3])
• dp 陣列變為：[7, 6, 10, 3]

第二輪迴圈 (i = 1)

• j = 0: dp[0] = triangle[1][0] + min(dp[0], dp[1])
• j = 1: dp[1] = triangle[1][1] + min(dp[1], dp[2])
• dp 陣列變為：[9, 10, 10, 3]

第三輪迴圈 (i = 0)

• j = 0: dp[0] = triangle[0][0] + min(dp[0], dp[1])
• dp 陣列變為：[11, 10, 10, 3]

迴圈結束

• 返回 dp[0]，結果為 11。

6. 相關題目與延伸概念

1054. Distant Barcodes

2957. Remove Adjacent Almost-Equal Characters

3161. Block Placement Queries

7. 補充：語法＆注意事項

記憶體使用模式

初始：dp = [4, 1, 8, 3] (最底層)
第2層：dp = [7, 6, 10, 3] (前3個有效)
第1層：dp = [9, 10, 10, 3] (前2個有效)
第0層：dp = [11, 10, 10, 3] (只有dp[0]有效)

和二維DP的對應關係

// 二維版本
dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1]);

// 一維版本（空間優化）
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);`

ps. 部分內容經 AI 協助整理