সমস্যা বিবৃতি
সংখ্যাগুলির একটি ত্রিভুজাকার কাঠামো দেওয়া হলে, উপরের থেকে নীচের সর্বনিম্ন পথের যোগফলটি সন্ধান করুন। প্রতিটি ধাপে আপনি নীচের সারিতে সংলগ্ন সংখ্যাগুলিতে যেতে পারেন।
উদাহরণ
যদি ইনপুট হয় −
5 7 3 8 1 2 9 6 4 5
তারপর ন্যূনতম যোগফল হল 13 নিম্নরূপ −
5 + 3 + 1 + 4
অ্যালগরিদম
- ডাইনামিক প্রোগ্রামিংয়ের মুখস্থ কৌশল ব্যবহার করুন
- মেমোরাইজেশনের জন্য 1-D অ্যারে তৈরি করুন, নাম মেমোরাইজেশন
- প্রতিটি K সারির জন্য নিচের সূত্রটি ব্যবহার করুন −
memorization[i] = min( memorization[i], memorization[i+1]) + A[k][i];
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMinSum(vector<vector<int>> &arr) {
int memorization[arr.size()];
int n = arr.size() - 1;
for (int i = 0; i < arr[n].size(); ++i) {
memorization[i] = arr[n][i];
}
for (int i = arr.size() - 2; i >= 0; --i) {
for (int j = 0; j < arr[i + 1].size() - 1; ++j) {
memorization[j] = arr[i][j] +
min(memorization[j],
memorization[j + 1]);
}
}
return memorization[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
