ในปัญหานี้ เราได้รับตัวเลขในรูปสามเหลี่ยมคว่ำ งานของเราคือสร้างโปรแกรมที่จะหาผลรวมเส้นทางสูงสุดในรูปสามเหลี่ยมคว่ำ
สามเหลี่ยมคว่ำ รูปแบบของตัวเลขเป็นการจัดเรียงเมื่อแถวแรกมีองค์ประกอบ 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
