C++ में मैट्रिक्स में पहली पंक्ति से अंतिम पंक्ति तक अधिकतम योग पथ

मैट्रिक्स दी गई है जहां चालें (i+1, j), (i+1, j-1), (i+1, j+1) हो सकती हैं। पहली पंक्ति के किसी सेल से शुरू करके अंतिम पंक्ति के किसी सेल तक अधिकतम योग पथ खोजें।

DP: dp[i][j] = सेल (i,j) तक अधिकतम योग। पहली पंक्ति आरंभ करें, फिर नीचे की पंक्तियों के लिए तीनों संभावित पूर्ववर्तियों से अधिकतम लें।

उदाहरण 4x4 मैट्रिक्स के लिए अधिकतम योग 120।

C++ कार्यान्वयन

#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