ประเมินการย้อนกลับสัญกรณ์โปแลนด์ใน C ++

สมมุติว่าเรามีสามเหลี่ยม เราต้องหาผลรวมเส้นทางขั้นต่ำจากบนลงล่าง ในแต่ละขั้นตอนเราสามารถย้ายไปยังตัวเลขที่อยู่ติดกันในแถวด้านล่างได้

ตัวอย่างเช่น ถ้ารูปสามเหลี่ยมต่อไปนี้มีลักษณะเหมือน

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

ผลรวมเส้นทางต่ำสุดจากบนลงล่างคือ 11 (2 + 3 + 5 + 1 =11)

มาดูขั้นตอนกันเลย

• สร้างตารางหนึ่งตารางเพื่อใช้ในแนวทางการเขียนโปรแกรมแบบไดนามิก
• n :=ขนาดของสามเหลี่ยม
• สำหรับ i :=n – 2 เหลือ 0
  • สำหรับ j :=0 ถึง i
    • dp[j] :=สามเหลี่ยม[i, j] + ค่าต่ำสุดของ dp[j] และ dp[j + 1]
• ผลตอบแทน dp[0]

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น

ตัวอย่าง

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]);
      }
      // printVector(dp);
   }
   return dp[0];
   }
};

อินพุต

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

ผลลัพธ์

11