ผลรวมเส้นทางสูงสุดในรูปสามเหลี่ยมคว่ำใน C ++

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

สามเหลี่ยมคว่ำ รูปแบบของตัวเลขเป็นการจัดเรียงเมื่อแถวแรกมีองค์ประกอบ n ตัว, n-1 ที่สอง และอื่นๆ

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

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน −

ป้อนข้อมูล −

5 1 9
 3 6
  2

ผลผลิต − 17

คำอธิบาย − ที่นี่ ฉันพบเส้นทางจากแถวสุดท้ายไปยังแถวบนสุด โดยพิจารณาจากองค์ประกอบสูงสุดที่เป็นไปได้ในเส้นทาง

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

ก่อนหน้านี้ เราจะพิจารณาสามเหลี่ยมคว่ำเป็นเมทริกซ์ปกติโดยเลื่อนจำนวนทางซ้ายทั้งหมดและเพิ่ม 0 ไปยังตำแหน่งที่เหลือ

ตัวอย่าง

โปรแกรมหาผลรวมเส้นทางสูงสุดในรูปสามเหลี่ยมคว่ำ −

#include <iostream>
using namespace std;
#define N 3
int findMaxPathSumInvertedTriangle(int matrix[][N]){
   int maxSum = 0;
   for (int i = N - 2; i >= 0; i--) {
      for (int j = 0; j < N - i; j++) {
         if (j - 1 >= 0)
            matrix[i][j] += max(matrix[i + 1][j], matrix[i + 1][j - 1]);
         else
            matrix[i][j] += matrix[i + 1][j];
            maxSum = max(maxSum, matrix[i][j]);
      }
   }
   return maxSum;
}
int main(){
   int invertedTriangle[N][N] = {
      {5, 1, 9},
      {3, 6, 0},
      {2, 0, 0}};
   cout<<"The maximum path sum is "<<findMaxPathSumInvertedTriangle(invertedTriangle);
   return 0;
}

ผลลัพธ์

The maximum path sum is 17