เส้นทางรวมขั้นต่ำในสามเหลี่ยมใน C++

คำชี้แจงปัญหา

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

ตัวอย่าง

หากอินพุตเป็น −

   5
  7 3
 8 1 2
9 6 4 5

แล้วผลรวมขั้นต่ำคือ 13 ดังนี้ −

5 + 3 + 1 + 4

อัลกอริทึม

• ใช้เทคนิคการท่องจำของโปรแกรมไดนามิก
• สร้างอาร์เรย์ 1-D สำหรับการท่องจำ คือ การท่องจำ
• สำหรับแต่ละแถว K ใช้สูตรด้านล่าง −

memorization[i] = min( memorization[i], memorization[i+1])
+ A[k][i];

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
int getMinSum(vector<vector<int>> &arr) {
   int memorization[arr.size()];
   int n = arr.size() - 1;
   for (int i = 0; i < arr[n].size(); ++i) {
      memorization[i] = arr[n][i];
   }
   for (int i = arr.size() - 2; i >= 0; --i) {
      for (int j = 0; j < arr[i + 1].size() - 1; ++j) {
         memorization[j] = arr[i][j] +
         min(memorization[j],
         memorization[j + 1]);
      }
   }
   return memorization[0];
}
int main() {
   vector<vector<int>> arr = {
   {5},
   {7, 3},
   {8, 1, 2},
   {9, 6, 4, 5}, };
   cout << "Minimum sum path = " << getMinSum(arr) << endl;
   return 0;
}

เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -

ผลลัพธ์

Minimum sum path = 13