ধরি arr একটি স্কোয়ার গ্রিড। নন-জিরো শিফ্ট সহ ফলিং পাথ হলো প্রতিটি সারি থেকে একটা করে এলিমেন্ট বেছে নেওয়া যাতে দুটি প্রতিবেশী সারি থেকে একই কলামে এলিমেন্ট নেওয়া না হয়। ন্যূনতম ফলিং পাথ সাম বের করতে হবে।
ইনপুট [[1,2,3],[4,5,6],[7,8,9]] হলে আউটপুট 13 (পাথ: 1→5→7)।
সমাধানের ধাপসমূহ
n := সারি, m := কলাম
i := 1 থেকে n-1 পর্যন্ত লুপ চালান –
leftMin এবং rightMin অ্যারে তৈরি করুন (সাইজ m)
leftMin[0] = arr[i-1][0], তারপর লেফট মিন কালকুলেট করুন
rightMin[m-1] = arr[i-1][m-1], তারপর রাইট মিন কালকুলেট করুন
j := 0 থেকে m-1 পর্যন্ত – leftVal এবং rightVal বের করে arr[i][j] আপডেট করুন
শেষ সারের ন্যূনতম ভ্যালু ফেরত দিন
বेहतर বোঝার জন্য নিচের কোডটি দেখুন –
উদাহরণ
#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
