ধরুন আমাদের একটি ত্রিভুজ আছে। আমাদের উপরের থেকে নীচের সর্বনিম্ন পথের যোগফল খুঁজে বের করতে হবে। প্রতিটি ধাপে, আমরা নীচের সারিতে সংলগ্ন সংখ্যায় যেতে পারি।
উদাহরণস্বরূপ, যদি নিচের ত্রিভুজটি
এর মত হয়[ [2], [3,4], [6,5,7], [4,1,8,3] ]
উপর থেকে নীচের সর্বনিম্ন পথের যোগফল হল 11 (2 + 3 + 5 + 1 =11)।
চলুন ধাপগুলো দেখি −
-
ডায়নামিক প্রোগ্রামিং পদ্ধতিতে ব্যবহার করার জন্য একটি টেবিল তৈরি করুন।
-
n :=ত্রিভুজের আকার
-
i এর জন্য :=n – 2 থেকে 0
নিচে-
j :=0 থেকে i
এর জন্য-
dp[j] :=ত্রিভুজ[i, j] + ন্যূনতম dp[j] এবং dp[j + 1]
-
-
-
dp[0]
ফেরত দিন
উদাহরণ(C++)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
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];
}
};
main(){
Solution ob;
vector<vector<int> > v = {{2},{3,4},{6,5,7},{4,1,8,3}};
cout << ob.minimumTotal(v);
} ইনপুট
[[2],[3,4],[6,5,7],[4,1,8,3]]
আউটপুট
11
