এই সমস্যায়, আমাদের সংখ্যাগুলো একটি উল্টো ত্রিভুজের আকারে দেওয়া আছে। আমাদের কাজ হলো একটি প্রোগ্রাম তৈরি করা যা উল্টো ত্রিভুজে সর্বোচ্চ পথ যোগফল বের করবে।
উল্টো ত্রিভুজ হলো এমন একটি সাজানো যেখানে প্রথম সারি nটি উপাদান থাকে, দ্বিতীয় সারি n-1টি, এবং এভাবে চলতে থাকে।
এখানে আমাদের প্রতিটি সারি থেকে একটি উপাদান নিয়ে সর্বোচ্চ যোগফল বের করতে হবে।
উদাহরণস্বরূপ সমস্যা বুঝতে নিচের উদাহরণটি দেখুন −
ইনপুট −
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
