इस समस्या में हमें एक उल्टे त्रिभुज के रूप में संख्याएँ दी जाती हैं। हमारा काम एक प्रोग्राम बनाना है जो उल्टे त्रिकोण में अधिकतम पथ योग ढूंढेगा।
उल्टा त्रिकोण संख्या का रूप एक व्यवस्था है जब पहली पंक्ति में n तत्व होते हैं, दूसरी n-1, और इसी तरह।
यहां, हमें अधिकतम योग ज्ञात करना है जो प्रत्येक पंक्ति में एक तत्व जोड़कर 3 प्राप्त किया जा सकता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं -
इनपुट -
5 1 9 3 6 2
आउटपुट − 17
स्पष्टीकरण - यहाँ, मैंने पथ में अधिकतम संभव तत्वों को ध्यान में रखते हुए, अंतिम पंक्ति से शीर्ष पंक्ति तक का रास्ता खोज लिया है।
इस समस्या को हल करने के लिए, हम गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे, जैसा कि हम न्यूनतम लागत पथ समस्याओं के मामले में लागू करते हैं। यहां, हम नीचे से शुरू करेंगे और फिर वह रास्ता खोजेंगे जो अधिकतम योग देता है।
इससे पहले, हम उल्टे त्रिकोण को एक नियमित मैट्रिक्स के रूप में मानेंगे, बाईं ओर की सभी संख्याओं को स्थानांतरित करके और शेष स्थानों में 0 जोड़ देंगे।
उदाहरण
एक उल्टे त्रिभुज में अधिकतम पथ योग ज्ञात करने का कार्यक्रम -
#include <iostream>
using namespace std;
#define N 3
int findMaxPathSumInvertedTriangle(int matrix[][N]){
int maxSum = 0;
for (int i = N - 2; i >= 0; i--) {
for (int j = 0; j < N - i; j++) {
if (j - 1 >= 0)
matrix[i][j] += max(matrix[i + 1][j], matrix[i + 1][j - 1]);
else
matrix[i][j] += matrix[i + 1][j];
maxSum = max(maxSum, matrix[i][j]);
}
}
return maxSum;
}
int main(){
int invertedTriangle[N][N] = {
{5, 1, 9},
{3, 6, 0},
{2, 0, 0}};
cout<<"The maximum path sum is "<<findMaxPathSumInvertedTriangle(invertedTriangle);
return 0;
} आउटपुट
The maximum path sum is 17