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