সমস্যা বিবরণ
সংখ্যার একটি ত্রিভুজাকার কাঠামো দেওয়া আছে। উপরে থেকে নিচে যেতে ন্যূনতম পথের যোগফল বের করতে হবে। প্রতিটি স্টেপে নিচের সারির আডজেসেন্ট সংখ্যাগুলোর যেকোনো একে বেছে নেওয়া যায়।
উদাহরণ
5
7 3
8 1 2
9 6 4 5
ন্যূনতম যোগফল ১৩ (৫ + ৩ + ১ + ৪)।
অ্যালগরিদম (ডাইনামিক প্রোগ্রামিং)
- মেমোরাইজেশন için ১-ডি অ্যারে ব্যবহার করুন।
- নিচের সারি থেকে শুরু করে উপরের দিকে যান। প্রতিটি সারি k-এর জন্য:
memo[i] = min(memo[i], memo[i+1]) + A[k][i]।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMinSum(vector<vector<int>> &arr) {
int n = arr.size();
vector<int> memo(arr[n-1].begin(), arr[n-1].end());
for (int i = n-2; i >= 0; --i) {
for (int j = 0; j < arr[i].size(); ++j) {
memo[j] = arr[i][j] + min(memo[j], memo[j+1]);
}
}
return memo[0];
}
int main() {
vector<vector<int>> arr = {{5}, {7,3}, {8,1,2}, {9,6,4,5}};
cout << "Minimum sum path = " << getMinSum(arr) << endl;
return 0;
}
আউটপুট
Minimum sum path = 13
