समस्या कथन
- आकार NxN का पूर्णांकों का मैट्रिक्स A दिया गया है। कार्य A के माध्यम से गिरते पथ का न्यूनतम योग खोजना है।
- एक गिरता पथ पहली पंक्ति में किसी भी तत्व से शुरू होगा और अंतिम पंक्ति में समाप्त होगा।
- यह प्रत्येक अगली पंक्ति से एक तत्व चुनता है। अगली पंक्ति का विकल्प पिछली पंक्ति के कॉलम से अधिकतम एक से भिन्न कॉलम में होना चाहिए
उदाहरण
यदि N = 2 और मैट्रिक्स है: { {5, 10}, {25, 15} } तो आउटपुट 20 होगा क्योंकि तत्व 5 और 15 चुने गए हैंउदाहरण
#include <bits/stdc++.h> #define MAX 2 using namespace std; int getMinSumPath(int matrix[MAX][MAX]) { for (int row = MAX - 2; row >= 0; --row) { for (int col = 0; col < MAX; ++col) { int val = matrix[row + 1][col]; if (col > 0) { val = min(val, matrix[row +1][col - 1]); } if (col + 1 < MAX) { val = min(val, matrix[row +1][col + 1]); } matrix[row][col] = matrix[row][col] +val; } } int result = INT_MAX; for (int i = 0; i < MAX; ++i) result = min(result, matrix[0][i]); return result; } int main() { int matrix[MAX][MAX] = { {5, 10}, {25, 15}, }; cout << "न्यूनतम योग पथ = " << getMinSumPath(matrix) << endl; return 0; }जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है
आउटपुट
न्यूनतम योग पथ = 20
