Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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

मान लीजिए हमारे पास एक ग्रिड arr है, यह एक वर्ग ग्रिड है, गैर-शून्य शिफ्ट के साथ एक गिरता पथ arr की प्रत्येक पंक्ति से ठीक एक तत्व का चयन है, जैसे कि आसन्न पंक्तियों में चुने गए कोई दो तत्व एक ही स्तंभ में मौजूद नहीं हैं। हमें गैर-शून्य शिफ्ट के साथ गिरते पथ का न्यूनतम योग ज्ञात करना है।

यदि इनपुट arr = [[1,2,3],[4,5,6],[7,8,9]] है, तो आउटपुट 13 होगा, क्योंकि विभिन्न गिरते पथ हैं जैसे [1,5,9], [1,5,7], [1,6,7], [1,6,8], [2,4,8], [2,4,9], [2,6,7], [2,6,8], [3,4,8], [3,4,9], [3,5,7], [3,5,9]। अब सबसे छोटे योग वाला गिरता पथ [1,5,7] है, इसलिए उत्तर 13 है।

हल करने के चरण

  • n := पंक्तियों की संख्या, m := स्तंभों की संख्या

  • पंक्ति 1 से n-1 तक के लिए: leftMin और rightMin सरणी की गणना करें

  • leftMin[0] := arr[i-1][0], leftMin[j] = min(leftMin[j-1], arr[i-1][j])

  • rightMin[m-1] = arr[i-1][m-1], rightMin[j] = min(arr[i-1][j], rightMin[j+1])

  • प्रत्येक स्तंभ j के लिए: leftVal = (j-1>=0 ? leftMin[j-1] : INF), rightVal = (j+1

  • अंतिम पंक्ति का न्यूनतम मान लौटाएं

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 

int dp[10005][205]; 

class Solution { 
public: 
    void pre() { 
        for(int i = 0; i <= 10000; i++) { 
            for(int j = 0; j <= 204; j++) { 
                dp[i][j] = -1; 
            } 
        } 
    } 
    int minFallingPathSum(vector<vector<int>>& arr) { 
        int n = arr.size(); 
        int m = arr[0].size(); 
        for (int i = 1; i < n; i++) { 
            vector<int> leftMin(m); 
            vector<int> rightMin(m); 
            leftMin[0] = arr[i - 1][0]; 
            for (int j = 1; j < m; j++) { 
                leftMin[j] = min(leftMin[j - 1], arr[i - 1][j]); 
            } 
            rightMin[m - 1] = arr[i - 1][m - 1]; 
            for (int j = m - 2; j >= 0; j--) { 
                rightMin[j] = min(arr[i - 1][j], rightMin[j + 1]); 
            } 
            for (int j = 0; j < m; j++) { 
                int leftVal = (j - 1) >= 0 ? leftMin[j - 1] : 1000000; 
                int rightVal = (j + 1) < m ? rightMin[j + 1] : 1000000; 
                arr[i][j] += min(leftVal, rightVal); 
            } 
        } 
        int ans = INT_MAX; 
        for (int i = 0; i < m; i++) ans = min(ans, arr[n - 1][i]); 
        return ans; 
    } 
}; 

int main() { 
    Solution ob; 
    vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}}; 
    cout << (ob.minFallingPathSum(v)); 
    return 0; 
}

इनपुट

{{1,2,3},{4,5,6},{7,8,9}}

आउटपुट

13
  1. C++ में पाथ सम III - रूट से लीफ तक दिए गए योग वाले पाथ ढूंढना C++ में पाथ सम III - रूट से लीफ तक दिए गए योग वाले पाथ ढूंढना

    मान लीजिए हमारे पास एक बाइनरी ट्री है जिसमें प्रत्येक नोड एक पूर्णांक मान रखता है। हमें उन पाथ को ढूंढना है जिनका योग दिए गए मान के बराबर हो। पाथ रूट से लीफ तक होना चाहिए। समस्या विवरण यदि ट्री है [5,4,8,11,null,13,4,7,2,null,null,5,1] और योग 22 है, तो परिणाम होगा - पाथ हैं: [[5,4,11,2],[5,8,4,5]

  1. C++ में बाइनरी ट्री में अधिकतम पथ योग C++ में बाइनरी ट्री में अधिकतम पथ योग

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है जिसमें प्रत्येक नोड एक मान रखता है। हमारा कार्य बाइनरी ट्री के दो पत्तों के बीच अधिकतम पथ योग ढूंढने के लिए एक प्रोग्राम बनाना है। यहां, हमें एक पत्ते नोड से दूसरे पत्ते नोड तक का पथ ढूंढना है जो मानों का अधिकतम योग प्रदान करेगा। यह अधिकतम योग पथ रूट न

  1. - पायथन में न्यूनतम पथ योग

    मान लीजिए हमारे पास एक m x n मैट्रिक्स है जो गैर-ऋणात्मक पूर्णांकों से भरा है, शीर्ष बाएं कोने से नीचे दाएं कोने तक एक पथ ढूंढें जो उसके पथ के साथ सभी संख्याओं के योग को न्यूनतम करता है। गतिविधियाँ किसी भी समय केवल नीचे या दाएं हो सकती हैं। इसलिए उदाहरण के लिए, यदि मैट्रिक्स नीचे जैसा है 131 151