สามเหลี่ยมใน 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]

ตัวอย่าง(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];
   }
};
main(){
   Solution ob;
   vector<vector<int> > v = {{2},{3,4},{6,5,7},{4,1,8,3}};
   cout << ob.minimumTotal(v);
}

อินพุต

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

ผลลัพธ์

11