দ্রষ্টব্য: আর্টিকেলের টাইটেলটি ভুল দেওয়া আছে। প্রকৃতপক্ষে এটি ট্রায়্যাঙ্গেলে মিনিমাম পাথ সম নির্ণয় সম্পর্কে।
একটি ট্রায়্যাঙ্গেল দেওয়া আছে। টপ থেকে বটম পর্যন্ত মিনিমাম পাথ সম বের করতে হবে। প্রতিটি স্টেপে নিচের রোয়ের এডজাসেন্ট নম্বরে যেতে পারব।
উদাহরণ: [[2],[3,4],[6,5,7],[4,1,8,3]] -> মিনিমাম পাথ সম = ১১ (2+3+5+1)।
সমাধান: DP টেবিল (বটম-আপ)। লাস্ট রো কপি করে উপরে চলে আসব। DP[j] = triangle[i][j] + min(DP[j], DP[j+1])।
উদাহরণ
class Solution {
public:
void printVector(vector <int>& v){
for(int i = 0; i < v.size(); i++) cout << v[i] << " ";
cout << endl;
}
int minimumTotal(vector<vector<int>>& triangle) {
vector <int> dp(triangle.back());
int n = triangle.size();
for(int i = n - 2; i >= 0; i--){
for(int j = 0; j <= i; j++){
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
}
}
return dp[0];
}
};
ইনপুট
[[2],[3,4],[6,5,7],[4,1,8,3]]
আউটপুট
11
