C++ এ উপরে থেকে নিচের দিকে ম্যাট্রিক্সে সর্বাধিক যোগফলের পথ

সমস্যা বিবৃতি

একটি n*n ম্যাট্রিক্স বিবেচনা করুন। ধরুন ম্যাট্রিক্সের প্রতিটি কক্ষের একটি মান নির্ধারণ করা আছে। আমরা সারির i এর প্রতিটি সেল থেকে শুধুমাত্র i+1 সারির একটি তির্যক উচ্চতর ঘরে যেতে পারি [যেমন সেল(i, j) টোসেল(i+1, j-1) এবং সেল (i+1, j+1) থেকে কেবল]. উপরের সারি থেকে নীচের সারিতে যাওয়ার পথটি পূর্বোক্ত শর্ত অনুসরণ করুন যাতে সর্বাধিক যোগফল পাওয়া যায়

উদাহরণ

If given input is:
{
   {5, 6, 1, 17},
   {-2, 10, 8, -1},
   { 3, -7, -9, 4},
   {12, -4, 2, 2}
}

সর্বাধিক যোগফল হল (17 + 8 + 4 + 2) =31

অ্যালগরিদম

• ধারণাটি হল সর্বাধিক যোগফল, বা প্রথম সারির প্রতিটি ঘর থেকে শুরু করে সমস্ত পাথ খুঁজে বের করা এবং শেষ পর্যন্ত প্রথম সারিতে সর্বাধিক সমস্ত মান ফেরত দেওয়া৷

• আমরা ডায়নামিক প্রোগ্রামিং ব্যবহার করি কারণ অনেক সাব সমস্যার ফলাফল বারবার প্রয়োজন হয়

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
int getMaxMatrixSum(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, 17},
      {-2, 10, 8, -1},
      {3, -7, -9, 4},
      {12, -4, 2, 2}
   };
   int n = 4;
   cout << "Maximum Sum = " << getMaxMatrixSum(mat, n) << endl;
   return 0;
}

আউটপুট

আপনি যখন উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি অনুসরণ করে আউটপুট-

Maximum Sum = 31