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

C++ में न्यूनतम फॉलिंग पथ योग


मान लीजिए हमारे पास पूर्णांकों का एक वर्ग सरणी A है, हम A के माध्यम से एक फॉलिंग पथ का न्यूनतम योग चाहते हैं। फॉलिंग पथ मूल रूप से एक पथ है जो पहली पंक्ति में किसी भी तत्व से शुरू होता है, और प्रत्येक पंक्ति से एक तत्व चुनता है। और अगली पंक्ति का तत्व पिछली पंक्ति के स्तंभ से अधिकतम एक अलग स्तंभ में होना चाहिए। उदाहरण के लिए, यदि मैट्रिक्स है:

123
456
789

तो आउटपुट 12 है। कुछ अलग फॉलिंग पथ हैं: [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9], [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,9], [3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9], और सबसे छोटा योग पथ [1,4,7] है जिसका योग 12 है।

हल करने के चरण

  • n := सरणी का आकार
  • i को n-2 से 0 तक नीचे लूप करें
    • j को 0 से n-1 तक लूप करें
      • यदि j-1 < 0, तो x1 := अनंत, अन्यथा x1 := matrix[i+1][j-1]
      • x2 := matrix[i+1][j]
      • यदि j+1 >= n, तो x3 := अनंत, अन्यथा x3 := matrix[i+1][j+1]
      • matrix[i][j] := matrix[i][j] + min(x1, x2, x3)
  • ans := अनंत
  • i को 0 से n-1 तक लूप करें
    • ans := min(ans, matrix[0][i])
  • ans वापस करें

उदाहरण

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int minFallingPathSum(vector<vector<int>>& a) {       int n = a.size();       for(int i =n-2;i>=0;i--){          for(int j =0;j<n;j++){             int x1 = j-1<0?INT_MAX:a[i+1][j-1];             int x2 = a[i+1][j];             int x3 = j+1>=n?INT_MAX:a[i+1][j+1];             a[i][j]+= min({x1,x2,x3});          }       }       int ans = INT_MAX;       for(int i =0;i<n;i++){          ans = min(ans,a[0][i]);       }       return ans;    } }; main(){    vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};    Solution ob;    cout <<(ob.minFallingPathSum(v)); }

इनपुट

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

आउटपुट

12
  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