मान लीजिए हमारे पास एक ग्रिड 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