C++ में त्रिकोण में न्यूनतम पथ योग (Minimum Path Sum in Triangle)

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

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

[
    [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] + dp[j] और dp[j + 1] का न्यूनतम
• dp[0] वापस करें

उदाहरण

class Solution {
public:
    void printVector(vector <int>& v){
        for(int i = 0; i < v.size(); i++) cout << v[i] << " ";
        cout << endl;
    }
    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];
    }
};

इनपुट

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

आउटपुट

11