Maximum Sum Path in Matrix - หาเส้นทางผลรวมสูงสุดในเมทริกซ์จากบนลงล่างใน C++

ปัญหา

มีเมทริกซ์ n×n แต่ละเซลล์มีค่า จากเซลล์ (i,j) ไปได้เฉพาะ (i+1,j-1) และ (i+1,j+1) หาเส้นทางจากแถวบนสุดถึงล่างสุดที่ให้ผลรวมสูงสุด

ตัวอย่าง

Matrix:
{5, 6, 1, 17}
{-2, 10, 8, -1}
{3, -7, -9, 4}
{12, -4, 2, 2}
Max Sum = 31 (17+8+4+2)

อัลกอริทึม (Dynamic Programming Bottom-up)

1. dp[n-1][j] = mat[n-1][j] (แถวสุดท้าย)
2. for i = n-2 ถึง 0:
   • for j = 0 ถึง n-1:
     • max = max(dp[i+1][j-1], dp[i+1][j+1]) (ถ้าอยู่ในขอบเขต)
     • dp[i][j] = mat[i][j] + max
3. คำตอบ = max(dp[0][j]) สำหรับทุก j

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

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

int getMaxMatrixSum(int mat[SIZE][SIZE], int n){
    if (n == 1) return mat[0][0];
    int dp[n][n];
    int maxSum = INT_MIN, max;
    for (int j = 0; j < n; j++) dp[n-1][j] = mat[n-1][j];
    for (int i = n-2; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            max = INT_MIN;
            if ((j-1) >= 0 && max < dp[i+1][j-1]) max = dp[i+1][j-1];
            if ((j+1) < n && max < dp[i+1][j+1]) max = dp[i+1][j+1];
            dp[i][j] = mat[i][j] + max;
        }
    }
    for (int j = 0; j < n; j++)
        if (maxSum < dp[0][j]) maxSum = dp[0][j];
    return maxSum;
}

int main(){
    int mat[SIZE][SIZE] = {
        {5, 6, 1, 17},
        {-2, 10, 8, -1},
        {3, -7, -9, 4},
        {12, -4, 2, 2}
    };
    int n = 4;
    cout << "Maximum Sum = " << getMaxMatrixSum(mat, n) << endl;
    return 0;
}

ผลลัพธ์

Maximum Sum = 31