सी++ में त्रिभुज में न्यूनतम योग पथ

समस्या कथन

संख्याओं की त्रिकोणीय संरचना को देखते हुए, ऊपर से नीचे तक न्यूनतम पथ योग ज्ञात करें। प्रत्येक चरण में आप नीचे की पंक्ति में आसन्न संख्याओं पर जा सकते हैं।

उदाहरण

अगर इनपुट है -

   5
  7 3
 8 1 2
9 6 4 5

फिर न्यूनतम योग 13 इस प्रकार है -

5 + 3 + 1 + 4

एल्गोरिदम

• गतिशील प्रोग्रामिंग की याद रखने की तकनीक का उपयोग करें
• याद रखने के लिए 1-डी सरणी बनाएं अर्थात् याद रखना
• प्रत्येक K पंक्ति के लिए नीचे दिए गए सूत्र का उपयोग करें -

memorization[i] = min( memorization[i], memorization[i+1])
+ A[k][i];

उदाहरण

#include <bits/stdc++.h>
using namespace std;
int getMinSum(vector<vector<int>> &arr) {
   int memorization[arr.size()];
   int n = arr.size() - 1;
   for (int i = 0; i < arr[n].size(); ++i) {
      memorization[i] = arr[n][i];
   }
   for (int i = arr.size() - 2; i >= 0; --i) {
      for (int j = 0; j < arr[i + 1].size() - 1; ++j) {
         memorization[j] = arr[i][j] +
         min(memorization[j],
         memorization[j + 1]);
      }
   }
   return memorization[0];
}
int main() {
   vector<vector<int>> arr = {
   {5},
   {7, 3},
   {8, 1, 2},
   {9, 6, 4, 5}, };
   cout << "Minimum sum path = " << getMinSum(arr) << endl;
   return 0;
}

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

आउटपुट

Minimum sum path = 13