এই সমস্যায়, আমাদেরকে ত্রিভুজ আকারে এমন সংখ্যা দেওয়া হয়েছে। আমাদের কাজ হল এমন একটি প্রোগ্রাম তৈরি করা যা একটি ত্রিভুজে সর্বাধিক পাথ যোগফল খুঁজে পাবে।
উপাদানগুলিকে 1ম সারি থেকে শুরু করে 1টি একটি উপাদান দিয়ে সাজানো হয় এবং তারপরে পরবর্তী সারিগুলি ক্রমবর্ধমান সংখ্যক উপাদান সহ nম সারিতে উপাদানগুলি না থাকা পর্যন্ত সাজানো হয়৷
সুতরাং, প্রোগ্রামটি এমন পথ খুঁজে পাবে যা ত্রিভুজের উপাদানগুলির সর্বাধিক যোগফল প্রদান করবে। সুতরাং, আমাদের এমন পথ খুঁজে বের করতে হবে যা সর্বোচ্চ যোগফল প্রদান করবে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক −
ইনপুট −
1 5 6 8 2 9
আউটপুট − 16
ব্যাখ্যা −
উপরের দিক থেকে পথটি সর্বোচ্চ যোগফল − 9+6+1 =16
প্রদান করবেএই সমস্যা সমাধানের জন্য, আমরা ডাইনামিক প্রোগ্রামিং ব্যবহার করব যা একটি বটম-আপ পদ্ধতি ব্যবহার করবে।
এর জন্য, আমরা প্রথমে ত্রিভুজের সমস্ত সংখ্যা স্থানান্তরিত করব এবং শেষে 0 যোগ করব। এটি ত্রিভুজটিকে একটি ম্যাট্রিক্সের মতো দেখাবে যা আমরা ন্যূনতম খরচের পথ সমস্যায় দেখি। এর পরে, আমরা নীচে থেকে শুরু করব, এবং প্রতিটি উপাদানের জন্য, আমরা সমস্ত সম্ভাব্য পাথ পরীক্ষা করব এবং সেই উপাদানটি পর্যন্ত সর্বাধিক সম্ভাব্য যোগফল প্রদান করে এমন পথ নির্বাচন করব। এবং ত্রিভুজে পথের সর্বাধিক সম্ভাব্য যোগফল খুঁজে পেতে একইভাবে শীর্ষে যান।
উদাহরণ
ত্রিভুজে সর্বাধিক পাথ যোগফল খুঁজে বের করার প্রোগ্রাম -
#include<iostream>
using namespace std;
#define N 3
int findMaxPathSumTriangle(int mat[][N], int m, int n){
for (int i=m-1; i>=0; i--){
for (int j=0; j<=i; j++){
if (mat[i+1][j] > mat[i+1][j+1])
mat[i][j] += mat[i+1][j];
else
mat[i][j] += mat[i+1][j+1];
}
}
return mat[0][0];
}
int main() {
int triangle[N][N] = {
{1, 0, 0},
{5, 6, 0},
{8, 2, 9} };
cout<<"The maximum path sum in triangle is "<<findMaxPathSumTriangle(triangle, 2, 2);
return 0;
} আউটপুট
The maximum path sum in triangle is 16
