समस्या कथन
संख्याओं का एक राइट ट्रायंगल दिया गया है, उन संख्याओं के योग का अधिकतम मान ढूंढें जो शीर्ष से आधार की ओर शुरू होने वाले पथों पर दिखाई देते हैं, ताकि प्रत्येक पथ पर अगली संख्या सीधे नीचे या नीचे-और-एक-स्थान-दाएं स्थित हो।
उदाहरण
यदि दिया गया इनपुट है: 3 4 5 1 10 7 तो अधिकतम योग 18 है (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 << "अधिकतम योग = " << maxSum(tringle, 3) << endl;
return 0;
}
आउटपुट
अधिकतम योग = 18