इस समस्या में, हमें संख्याएँ उल्टे त्रिभुज के रूप में दी गई हैं। हमारा कार्य एक प्रोग्राम बनाना है जो उल्टे त्रिभुज में अधिकतम पथ योग ढूंढेगा।
उल्टा त्रिभुज संख्याओं की एक व्यवस्था है जहां पहली पंक्ति में n तत्व होते हैं, दूसरी में n-1, और इसी तरह।
यहां, हमें प्रत्येक पंक्ति से एक तत्व जोड़कर प्राप्त होने वाला अधिकतम योग ढूंढना है।
आइए एक उदाहरण से इस समस्या को समझते हैं -
इनपुट -
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
