Triangle ใน C++: หา Minimum Path Sum จากบนลงล่าง

โจทย์

Triangle array หา minimum path sum จากบนลงล่าง แต่ละขั้นเดินได้เฉพาะ adjacent ในแถวถัดไป

ตัวอย่าง: [[2],[3,4],[6,5,7],[4,1,8,3]] → 11 (2+3+5+1)

แนวคิด: Bottom-up DP (In-place)

เริ่มจากแถวสุดท้าย-1 ขึ้นบน: dp[j] = triangle[i][j] + min(dp[j], dp[j+1])

ขั้นตอน

1. dp = triangle.back() (copy แถวสุดท้าย)
2. ลูป i = n-2 ถึง 0:
   • ลูป j = 0 ถึง i:
     • dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
3. คืน dp[0]

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

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

int main() {
    Solution ob;
    vector<vector<int>> v = {{2},{3,4},{6,5,7},{4,1,8,3}};
    cout << ob.minimumTotal(v); // 11
    return 0;
}

อินพุต / เอาต์พุต

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

Output: 11

ความซับซ้อน

• Time: O(n²) - n = จำนวนแถว
• Space: O(n) - array dp ขนาดแถวสุดท้าย