मान लीजिए हमारे पास पूर्णांकों का एक वर्ग सरणी A है, हम A के माध्यम से एक फॉलिंग पथ का न्यूनतम योग चाहते हैं। फॉलिंग पथ मूल रूप से एक पथ है जो पहली पंक्ति में किसी भी तत्व से शुरू होता है, और प्रत्येक पंक्ति से एक तत्व चुनता है। और अगली पंक्ति का तत्व पिछली पंक्ति के स्तंभ से अधिकतम एक अलग स्तंभ में होना चाहिए। उदाहरण के लिए, यदि मैट्रिक्स है:
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
तो आउटपुट 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)
- j को 0 से n-1 तक लूप करें
- 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