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

সমস্যা বিবরণ

একটি N×N ম্যাট্রিক্স দেওয়া থাকলে, উপরের সারি থেকে নিচের সারি পর্যন্ত যাওয়ার পথে সর্বোচ্চ সম বের করতে হবে। যাওয়ার নিয়ম: নিচের সারিতে ডায়াগোনালি (j-1 বা j+1) যাওয়া যাবে।

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

1. dp[n-1][j] = mat[n-1][j] (নিচের সারি ইনিশিয়ালাইজ)۔
2. i = n-2 থেকে 0 পর্যন্ত পিছিয়ে আসুন।
3. প্রতি j-এর জন্য: max = max(dp[i+1][j-1], dp[i+1][j+1]) (বাউন্ড চেক করে)।
4. dp[i][j] = mat[i][j] + max।
5. শেষে dp[0][j]-এর সর্বোচ্চ মান রিটার্ন করুন।

C++ কোড উদাহরণ

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

#define SIZE 10

int maxSum(int mat[SIZE][SIZE], int n) {
    if (n == 1) return mat[0][0];
    int dp[n][n];
    int maxSum = INT_MIN, max;
    
    for (int j = 0; j < n; j++)
        dp[n - 1][j] = mat[n - 1][j];
    
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            max = INT_MIN;
            if ((j - 1) >= 0 && max < dp[i + 1][j - 1]) max = dp[i + 1][j - 1];
            if ((j + 1) < n && max < dp[i + 1][j + 1]) max = dp[i + 1][j + 1];
            dp[i][j] = mat[i][j] + max;
        }
    }
    for (int j = 0; j < n; j++)
        if (maxSum < dp[0][j]) maxSum = dp[0][j];
    return maxSum;
}

int main() {
    int mat[SIZE][SIZE] = {
        {5, 6, 1, 7},
        {-2, 10, 8, -1},
        {3, -7, -9, 11},
        {12, -4, 2, 6}
    };
    int n = 4;
    cout << "Maximum Sum = " << maxSum(mat, n);
    return 0;
}

আউটপুট

Maximum Sum = 28

জটিলতা

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