C++ में त्रिकोण न्यूनतम पथ योग

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

उदाहरण के लिए, यदि निम्नलिखित त्रिकोण है:

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

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

चरण

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

• n := त्रिकोण का आकार

• i := n-2 से 0 तक नीचे जाएं

  • j := 0 से i तक

    • dp[j] := triangle[i][j] + min(dp[j], dp[j+1])

• dp[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