Tổng lớn nhất đường đi trong ma trận từ hàng đầu đến hàng cuối trong C++

Cho ma trận N×N. Tìm đường đi từ hàng 0 đến hàng N-1 với tổng lớn nhất, chỉ được di chuyển xuống hàng dưới: chéo trái, thẳng, hoặc chéo phải.

Thuật toán (DP bottom-up)

• dp[i][j]: tổng lớn nhất từ ô (i,j) đến hàng cuối.
• Khởi tạo hàng cuối: dp[N-1][j] = mat[N-1][j].
• Duyệt ngược từ hàng N-2 về 0: dp[i][j] = mat[i][j] + max(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]) (kiểm tra biên).
• Kết quả: max của hàng 0.

Ví dụ triển khai (C++)

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

int maxSum(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];
            if (max < dp[i+1][j]) max = dp[i+1][j];
            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, 7},
        {-2, 10, 8, -1},
        {3, -7, -9, 11},
        {12, -4, 2, 6}
    };
    int n = 4;
    cout << "Maximum Sum = " << maxSum(mat, n);
    return 0;
}

Đầu ra

Maximum Sum = 28