Maximum path sum that starting with any cell of 0-th row and ending with any cell of (N-1)-th row in C++

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมหาผลรวมเส้นทางสูงสุดที่เริ่มจากเซลล์ใดก็ได้ของแถว 0 และจบที่เซลล์ใดก็ได้ของแถว N-1

เราจะได้รับเมทริกซ์ที่มีการเคลื่อนที่เป็นไปได้ (i+1, j), (i+1, j-1), (i+1, j+1) งานคือเริ่มจากตำแหน่งแถว 0 และเคลื่อนที่ไปแถวสุดท้ายหาเส้นทางผลรวมสูงสุด

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

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

#define N 4

int MaximumPath(int Mat[][N]) {
    int result = 0;
    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], max(dp[i-1][j], dp[i-1][j+1])) + Mat[i][j-1];
    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;
}

เอาต์พุต

120