Minimum Path Sum ใน Triangle - หาผลรวมเส้นทางน้อยที่สุดในสามเหลี่ยมใน C++

ภาพรวมปัญหา

มีสามเหลี่ยมตัวเลข หาผลรวมเส้นทางน้อยที่สุดจากยอดถึงฐาน เคลื่อนที่ได้เฉพาะลงซ้ายหรือลงขวา

ตัวอย่าง

[
  [2],
  [3,4],
  [6,5,7],
  [4,1,8,3]
]
Output: 11 (2+3+5+1)

อัลกอริทึม (DP Bottom-up)

1. dp = คัดลอกแถวสุดท้ายของสามเหลี่ยม
2. for i = n-2 ถึง 0 (ขึ้นมาจากแถวก่อนสุดท้าย):
   • for j = 0 ถึง i:
     • dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
3. return dp[0]

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

class Solution {
public:
    void printVector(vector <int>& v){
        for(int i = 0; i < v.size(); i++) cout << v[i] << " ";
        cout << endl;
    }
    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];
    }
};

Input / Output

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