सी++ में न्यूनतम गिरने वाला पथ योग

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

फिर आउटपुट 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 :=सरणी का आकार
• के लिए मैं श्रेणी n - 2 में 0 से नीचे
  • जे के लिए 0 से n की सीमा में
    • यदि j - 1 <0, तो x1 :=inf, अन्यथा x1 :=मैट्रिक्स [i + 1, j - 1]
    • x2:=मैट्रिक्स[i + 1, j]
    • यदि j + 1>=n, तो x3 :=inf, अन्यथा x3 :=मैट्रिक्स [i + 1, j + 1]
    • मैट्रिक्स[i, j] :=मैट्रिक्स[i, j] + न्यूनतम x1, x2, x3
• उत्तर:=जानकारी
• मैं के लिए 0 से n - 1 की सीमा में
  • उत्तर:=उत्तर और मैट्रिक्स का मिनट[0, i]
• वापसी उत्तर

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

उदाहरण

#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