Tổng đường đi lớn nhất từ hàng 0 đến hàng N-1 trong ma trận C++

Cho ma trận N×N. Từ hàng 0 bất kỳ cột, đi đến hàng N-1, mỗi bước xuống hàng dưới: cùng cột, chéo trái, chéo phải. Tìm đường đi tổng lớn nhất.

Thuật toán (DP)

• dp[i][j]: tổng lớn nhất đến ô (i,j).
• Khởi tạo hàng 0: dp[0][j] = mat[0][j].
• Chuyển trạng thái: dp[i][j] = mat[i][j] + max(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]).
• Kết quả: max hàng cuối.

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

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

int MaximumPath(int Mat[][N]) {
    int dp[N][N+2];
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < N; i++) dp[0][i+1] = Mat[0][i];
    for (int i = 1; i < N; i++)
        for (int j = 1; j <= N; j++)
            dp[i][j] = max({dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]}) + Mat[i][j-1];
    int result = 0;
    for (int i = 0; i <= N; i++) result = max(result, dp[N-1][i]);
    return result;
}

int main() {
    int Mat[4][4] = {{4,2,3,4},{2,9,1,10},{15,1,3,0},{16,92,41,44}};
    cout << MaximumPath(Mat) << endl;
    return 0;
}

Đầu ra

120