সমস্যা বিবৃতি
- NxN আকারের পূর্ণসংখ্যার একটি ম্যাট্রিক্স A দেওয়া হয়েছে। কাজটি হল A. এর মাধ্যমে পতিত পথের ন্যূনতম যোগফল খুঁজে বের করা
- পতনের পথ প্রথম সারির যেকোনো উপাদান থেকে শুরু হবে এবং শেষ সারিতে শেষ হবে।
- এটি প্রতিটি পরবর্তী সারি থেকে একটি উপাদান বেছে নেয়। পরবর্তী সারির পছন্দটি এমন একটি কলামে হতে হবে যা পূর্ববর্তী সারির কলাম থেকে বেশির ভাগের দ্বারা আলাদা
উদাহরণ
If N = 2 and matrix is:
{
{5, 10},
{25, 15}
} then output will be 20 as element 5 and 15 are selected উদাহরণ
#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
