C++ में त्रिभुज

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

उदाहरण के लिए, यदि निम्न त्रिभुज इस प्रकार है

[
      [2],
     [3,4],
    [6,5,7],
   [4,1,8,3]
]

ऊपर से नीचे तक का न्यूनतम पथ योग 11 (2 + 3 + 5 + 1 =11) है।

आइए चरण देखें -

• गतिशील प्रोग्रामिंग दृष्टिकोण में उपयोग करने के लिए एक तालिका बनाएं।

• n :=त्रिभुज का आकार

• मैं के लिए :=n – 2 नीचे से 0 तक

  • j के लिए:=0 से i

    • dp[j] :=त्रिकोण [i, j] + न्यूनतम dp[j] और dp[j + 1]

• वापसी डीपी [0]

उदाहरण(C++)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minimumTotal(vector<vector<int>>& triangle) {
      vector <int> dp(triangle.back());
      int n = triangle.size();
      for(int i = n - 2; i >= 0; i--){
         for(int j = 0; j <= i; j++){
            dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
         }
      }
      return dp[0];
   }
};
main(){
   Solution ob;
   vector<vector<int> > v = {{2},{3,4},{6,5,7},{4,1,8,3}};
   cout << ob.minimumTotal(v);
}

इनपुट

[[2],[3,4],[6,5,7],[4,1,8,3]]

आउटपुट

11