স্কোয়ার ম্যাট্রিক্স A দেওয়া। প্রথম রো থেকে যেকোনো সেল দিয়ে শুরু করে নিচের রোতে কলাম পার্থক্য সর্বোচ্চ ১ রেখে একই বা আডজেসেন্ট কলামে যেতে হবে। ন্যূনতম পাথ সম বের করতে হবে।
উদাহরণ: [[1,2,3],[4,5,6],[7,8,9]] → ১২ (পাথ: 1→4→7)।
সমাধানের ধাপসমূহ
- বটম-আপ DP: নিচের রো থেকে উপরে যান।
a[i][j] += min(a[i+1][j-1], a[i+1][j], a[i+1][j+1])(বাউন্ডারি চেক সহ)।- শেষে প্রথম রোর মিনিমাম রিটার্ন করুন।
C++ উদাহরণ
#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 x : a[0]) ans = min(ans, x);
return ans;
}
};
int 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
