เส้นทางน้ำหนักสูงสุดที่สิ้นสุดที่องค์ประกอบใดๆ ของแถวสุดท้ายในเมทริกซ์ใน C++

ในปัญหานี้ เราได้รับจำนวนเต็ม n และเมทริกซ์ขนาด n X n ซึ่งมีน้ำหนักของเซลล์ งานของเราคือสร้างโปรแกรมที่จะหาเส้นทางน้ำหนักสูงสุดที่สิ้นสุดที่องค์ประกอบใดๆ ของแถวสุดท้ายในเมทริกซ์ ในการหาเส้นทาง การเดินทางจะเริ่มจากมุมซ้ายบน (0,0) และการเคลื่อนที่ที่ถูกต้องจะเป็นลงและทแยงมุม ไม่มีการเคลื่อนที่ไปทางซ้าย

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

อินพุต -

n = 3 Mat[3][3] ={ 
    {4, 3, 1}
    {5, 8, 9}
    {6, 7, 2}}

เอาต์พุต -

19

คำอธิบาย -

เส้นทางทั้งหมดที่สามารถใช้ได้จะเป็น
Path1: 4+5+6 = 15
Path2: 4+8+7 = 19
Path3: 4+8+2 = 12
Path4: 4+5+7 = 16

เนื่องจากที่ดีที่สุดคือ path2 ที่มีน้ำหนัก 19

ดังนั้น วิธีแก้ปัญหาที่เป็นไปได้หนึ่งคือการคำนวณเส้นทางทั้งหมดแล้วเปรียบเทียบ แต่วิธีนี้จะไม่มีประสิทธิภาพเมื่อ n เป็นจำนวนมาก

วิธีแก้ปัญหาที่มีประสิทธิภาพจะเป็นการใช้ Dynamic Programming เนื่องจากนี่เป็นปัญหาที่มีซับปัญหาทับซ้อนกัน เริ่มจากรากมี n สาขาที่สามารถให้ผลลัพธ์ที่ต้องการได้

เราจะสร้างเมทริกซ์ที่จะเก็บน้ำหนักสูงสุดของเส้นทางที่กำหนดซึ่งถูกเดินทางเพื่อไปถึงเซลล์นั้นในเมทริกซ์

จากนั้นเราจะรู้ว่าผลรวมสูงสุดอยู่ในแถวสุดท้ายของเมทริกซ์และพิมพ์มันออกมา

ตัวอย่างโค้ด

โปรแกรมแก้ปัญหา:

#include<bits/stdc++.h>
using namespace std;

const int MAX = 1000;

int maxCost(int matrix[][MAX], int N) {
    int sumMat[N][N];
    memset(sumMat, 0, sizeof(sumMat));
    int maxSum = 0;
    sumMat[0][0] = matrix[0][0];
    for (int i=1; i<N; i++)
        sumMat[i][0] = matrix[i][0] + sumMat[i-1][0];
    for (int i=1; i<N; i++)
    for (int j=1; j<i+1&&j<N; j++)
        sumMat[i][j] = matrix[i][j] + max(sumMat[i-1][j-1], sumMat[i-1][j]);
    for (int i=0; i<N; i++)
        if (maxSum < sumMat[N-1][i]) maxSum = sumMat[N-1][i];
    return maxSum;
}

int main(){
    int mat[MAX][MAX] ={
        {5 , 6 , 1 },
        {2 , 11 , 10 },
        {15, 3 , 2 }};
    int N = 3;
    cout<<"Maximum Path Sum for top-left cell to last row is : "<<maxCost(mat, N)<<endl;
    return 0;
}

ผลลัพธ์

Maximum Path Sum for top-left cell to last row is : 22