ধরুন আমাদের একটি গ্রিড 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 :=কলামের সংখ্যা
-
আরম্ভ করার জন্য i :=1, যখন i
-
m
সাইজের লেফটমিন এবং রাইটমিন অ্যারে সংজ্ঞায়িত করুন -
leftMin[0] :=arr[i - 1, 0]
-
j শুরু করার জন্য :=1, যখন j
-
leftMin[j] :=সর্বনিম্ন leftMin[j - 1] এবং arr[i - 1, j]
-
-
rightMin[m - 1] =arr[i - 1, m - 1]
-
j শুরু করার জন্য :=m - 2, যখন j>=0, আপডেট করুন (j 1 দ্বারা কম করুন), −
-
rightMin[j] :=ন্যূনতম arr[i - 1, j] এবং rightMin[j + 1]
-
-
j শুরু করার জন্য :=0, যখন j
-
leftVal :=(যদি (j - 1)>=0, তারপর leftMin[j - 1], অন্যথায় 1000000)
-
rightVal :=(যদি (j + 1)
-
arr[i, j] :=arr[i, j] + min(leftVal, rightVal)
-
-
-
উত্তর :=inf
-
আরম্ভ করার জন্য i :=0, যখন i
-
উত্তর :=সর্বনিম্ন উত্তর এবং arr[n - 1, i]
-
-
উত্তর ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};
cout << (ob.minFallingPathSum(v));
} ইনপুট
{{1,2,3},{4,5,6},{7,8,9}} আউটপুট
13
