C++-এ ম্যাট্রিক্সে সর্বোচ্চ ওজন পথ (Maximum Weight Path Ending at Last Row)

এই সমস্যাতে, একটি n×n ম্যাট্রিক্স দেওয়া থাকে যেখানে প্রতিটি সেলের ওজন আছে। আমাদের কাজ হল উপরের বাম কোণা (0,0) থেকে শুরু করে শেষ সারারো (last row)-এর যেকোনো সেল পর্যন্ত যাওয়ার সর্বোচ্চ ওজনবিশিষ্ট পথ বের করা। বৈধ 무ভ হলো নিচে (down) এবং ডায়াগোনাল (diagonal) — বামে যাওয়া যাবে না।

উদাহরণ

ইনপুট:

n = 3
Mat[3][3] = {
    {4, 3, 1},
    {5, 8, 9},
    {6, 7, 2}
}

আউটপুট: 19

ব্যাখ্যা:

Path 1: 4+5+6 = 15
Path 2: 4+8+7 = 19  ← সর্বোচ্চ
Path 3: 4+8+2 = 12
Path 4: 4+5+7 = 16

ডাইনামিক প্রোগ্রামিং সমাধান

একটি DP টেবিল তৈরি করুন যেখানে sumMat[i][j] = (i,j) সেল পর্যন্ত পৌঁছানোর সর্বোচ্চ ওজন।

sumMat[0][0] = matrix[0][0]
প্রথম কলাম: sumMat[i][0] = matrix[i][0] + sumMat[i-1][0]
অন্যান্য: sumMat[i][j] = matrix[i][j] + max(sumMat[i-1][j-1], sumMat[i-1][j])
শেষ সারারোয়ের সর্বোচ্চ মানই উত্তর

C++ প্রোগ্রাম উদাহরণ

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

const int MAX = 1000;

int maxCost(int matrix[][MAX], int N) {
    int sumMat[N][N];
    memset(sumMat, 0, sizeof(sumMat));
    int maxSum = 0;
    
    sumMat[0][0] = matrix[0][0];
    for (int i = 1; i < N; i++)
        sumMat[i][0] = matrix[i][0] + sumMat[i-1][0];
    
    for (int i = 1; i < N; i++)
        for (int j = 1; j < i+1 && j < N; j++)
            sumMat[i][j] = matrix[i][j] + max(sumMat[i-1][j-1], sumMat[i-1][j]);
    
    for (int i = 0; i < N; i++)
        if (maxSum < sumMat[N-1][i]) maxSum = sumMat[N-1][i];
    
    return maxSum;
}

int main() {
    int mat[MAX][MAX] = {
        {5, 6, 1},
        {2, 11, 10},
        {15, 3, 2}
    };
    int N = 3;
    cout << "Maximum Path Sum for top-left cell to last row is: " << maxCost(mat, N) << endl;
    return 0;
}

আউটপুট

Maximum Path Sum for top-left cell to last row is: 22