Tổng đường đi lớn nhất trong ma trận C++

Cho ma trận 2D kích thước M×N. Tìm tổng đường đi lớn nhất từ hàng đầu tiên đến hàng cuối cùng. Di chuyển cho phép: xuống (down), chéo trái (down-left), chéo phải (down-right). Điểm bắt đầu/kết thúc bất kỳ ở hàng đầu/cuối.

Ví dụ

Ma trận: 3 5 9 1 7 2 4 8 6 → Output: 24 (đường đi: 9 → 7 → 8)

Thuật toán Quy hoạch động

Cập nhật ma trận từ hàng 2 đến hàng cuối: mỗi ô cộng thêm max của 3 ô có thể đến từ hàng trên. Cuối cùng lấy max của hàng cuối.

Ví dụ minh họa

#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;
}

Kết quả

The maximum path sum of matrix is: 24

Độ phức tạp: O(M×N) thời gian, O(1) không gian thêm (sửa trực tiếp trên ma trận).