C++-এ ম্যাট্রিক্স-এ ০-রো থেকে N-1-রো পর্যন্ত যেতে সর্বোচ্চ পাথ সম বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি N×N ম্যাট্রিক্স দেওয়া থাকলে, ০-রো থেকে যেকোনো সেল দিয়ে শুরু করে N-1-রো-এ যেকোনো সেলে শেষ করতে হবে। মুভ: (i+1, j), (i+1, j-1), (i+1, j+1)। সর্বোচ্চ পাথ সম বের করুন।

সমাধানের পদ্ধতি (DP)

1. dp[i][j] = (i,j) সেলে পৌঁছাতে সর্বোচ্চ সম।
2. বেস: dp[0][j] = Mat[0][j]।
3. ট্রানজিশন: dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + Mat[i][j]।
4. উত্তর = max(dp[N-1][j]) সব j-এর জন্য।

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

ব্যাখ্যা

পাথ: 4 (0,0) → 9 (1,1) → 15 (2,0) → 92 (3,1) = 120? Wait, let me trace: 4→9→15→92 = 120. Yes.

জটিলতা

• সময়: O(N²)
• স্থান: O(N²)