সমস্যা বিবরণ
- NxN আকারের একটি ইন্টিজার ম্যাট্রিক্স A দেওয়া আছে। এর মাধ্যমে ফলিং পাথের ন্যূনতম সম বের করতে হবে।
- ফলিং পাথ প্রথম সারির যেকোনো এলিমেন্ট থেকে শুরু হয় এবং শেষ সারিতে শেষ হয়।
- এটি প্রতিটি পরবর্তী সারি থেকে একটি এলিমেন্ট বেছে নেয়। পরবর্তী সারির চয়েস অবশ্যই আগের সারির কলাম থেকে সর্বোচ্চ ১ টি কলাম ভিন্ন হতে পারে।
উদাহরণ
যদি N = 2 এবং ম্যাট্রিক্স হয়: { {5, 10}, {25, 15} } তবে আউটপুট হবে ২০ কারণ এলিমেন্ট ৫ এবং ১৫ নির্বাচিত হয়েছে
উদাহরণ
#include <bits/stdc++.h>
#define MAX 2
using namespace std;
int getMinSumPath(int matrix[MAX][MAX]) {
for (int row = MAX - 2; row >= 0; --row) {
for (int col = 0; col < MAX; ++col) {
int val = matrix[row + 1][col];
if (col > 0) {
val = min(val, matrix[row +1][col - 1]);
}
if (col + 1 < MAX) {
val = min(val, matrix[row +1][col + 1]);
}
matrix[row][col] = matrix[row][col] + val;
}
}
int result = INT_MAX;
for (int i = 0; i < MAX; ++i)
result = min(result, matrix[0][i]);
return result;
}
int main() {
int matrix[MAX][MAX] = {
{5, 10},
{25, 15},
};
cout << "Minimum sum path = " << getMinSumPath(matrix) << endl;
return 0;
}
উপরের প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট জেনারেট হবে
আউটপুট
Minimum sum path = 20
