अधिकतम पथ योग जो 0-वें पंक्ति के किसी भी सेल से शुरू होता है और C++ में (N-1)-वें पंक्ति के किसी भी सेल के साथ समाप्त होता है

इस ट्यूटोरियल में, हम अधिकतम पथ योग खोजने के लिए एक प्रोग्राम पर चर्चा करेंगे जो 0-वें पंक्ति के किसी भी सेल से शुरू होकर (N-1)-वें पंक्ति के किसी भी सेल पर समाप्त होगा

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

उदाहरण

#include<bits/stdc++.h>
using namespace std;
#define N 4
//finding maximum sum path
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