ผลรวมเส้นทางสูงสุดในเมทริกซ์ใน C++

บทนำ

ในปัญหานี้ เราได้รับเมทริกซ์ 2D ขนาด M×N มา ภารกิจคือสร้างโปรแกรมหาผลรวมเส้นทางสูงสุดในเมทริกซ์

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

ตัวอย่าง

อินพุต -

matrix[][] =  3 5 9
              1 7 2
              4 8 6

เอาต์พุต - 24

คำอธิบาย - เส้นทางสูงสุดคือ 9 → 7 → 8

เพื่อแก้ปัญหา เราจะเริ่มจากบนสุดของอาร์เรย์ หาองค์ประกอบมากที่สุดของแถวแรก เก็บใน maxSum จากนั้นเดินทางผ่านเมทริกซ์หาค่าสูงสุดที่เกิดในเส้นทาง หากค่าใหม่มากกว่า อัปเดต maxSum มิฉะนั้นไม่อัปเดต และเมื่อเดินทางครบทุกเมทริกซ์และสร้างเส้นทางแล้ว คืนค่า maxSum

ตัวอย่างโปรแกรม

#include <iostream>
#define N 3
#define M 3
using namespace std;

int maxPathSum(int mat[][M]) {
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (j > 0 && j < M - 1)
                mat[i][j] += max(mat[i-1][j], max(mat[i-1][j-1], mat[i-1][j+1]));
            else if (j > 0)
                mat[i][j] += max(mat[i-1][j], mat[i-1][j-1]);
            else if (j < M - 1)
                mat[i][j] += max(mat[i-1][j], mat[i-1][j+1]);
        }
    }
    int maxSum = mat[N-1][0];
    for (int j = 1; j < M; j++)
        maxSum = max(mat[N-1][j], maxSum);
    return maxSum;
}

int main() {
    int matrix[N][M] = {
        {3, 5, 9},
        {1, 7, 2},
        {4, 8, 6}
    };
    cout << "The maximum path sum of matrix is : " << maxPathSum(matrix);
    return 0;
}

ผลลัพธ์

The maximum path sum of matrix is : 24

คำอธิบาย

อัลกอริทึมใช้ Dynamic Programming แบบ Bottom-up อัปเดตค่าในเมทริกซ์เดิม (In-place) โดยแต่ละเซลล์จะบวกค่าสูงสุดจาก 3 ทิศทางที่มาจากแถวก่อนหน้า (ซ้ายบน, บน, ขวาบน) ท้ายสุดหาค่าสูงสุดในแถวสุดท้าย