C++ में एक सम संख्या त्रिभुज में पथ का अधिकतम योग

समस्या कथन

संख्याओं के एक समकोण त्रिभुज को देखते हुए, ऊपर से आधार की ओर जाने वाले पथों पर दिखाई देने वाली संख्याओं के योग का सबसे बड़ा योग ज्ञात कीजिए, ताकि प्रत्येक पथ पर अगली संख्या सीधे नीचे या नीचे-और-एक-स्थान पर स्थित हो। -द-राइट

उदाहरण

If given input is:
3
4 5
1 10 7
Then maximum sum is 18 as (3 + 5 + 10).

एल्गोरिदम

विचार यह है कि अंतिम पंक्ति के प्रत्येक सेल पर समाप्त होने वाली सबसे बड़ी राशि का पता लगाया जाए और इनमें से अधिकतम राशि लौटा दी जाए।

हम उपरोक्त दो कक्षों पर पुनरावर्ती रूप से विचार करके इन राशियों की पुनरावर्ती गणना कर सकते हैं

चूंकि ओवरलैपिंग उप-समस्याएं हैं, हम अंतिम पंक्ति के विशेष सेल पर अधिकतम योग समाप्त करने के लिए गतिशील प्रोग्रामिंग का उपयोग करते हैं

उदाहरण

#include<bits/stdc++.h>
using namespace std;
int maxSum(int tringle[][3], int n){
   if (n > 1) {
      tringle[1][1] = tringle[1][1] + tringle[0][0];
      tringle[1][0] = tringle[1][0] + tringle[0][0];
   }
   for(int i = 2; i < n; i++) {
      tringle[i][0] = tringle[i][0] + tringle[i-1][0];
      tringle[i][i] = tringle[i][i] + tringle[i-1][i-1];
      for (int j = 1; j < i; j++){
         if (tringle[i][j] + tringle[i-1][j-1] >=tringle[i][j] + tringle[i-1][j]) {
            tringle[i][j] = tringle[i][j] + tringle[i-1][j-1];
         } else {
            tringle[i][j] = tringle[i][j]+tringle[i-1][j];
         }
      }
   }
   int max = tringle[n - 1][0];
   for(int i = 1;i < n; i++) {
      if(max < tringle[n-1][i]) {
         max=tringle[n-1][i];
      }
   }
   return max;
}
int main(){
   int tringle[3][3] = {
      {3},
      {4,5},
      {1,10,7}
   };
   cout << "Maximum sum = " << maxSum(tringle, 3) << endl;
   return 0;
}

आउटपुट

जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -

Maximum sum = 18