এই সমস্যায়, আমাদের সংখ্যাগুলো একটি ত্রিভুজের আকারে দেওয়া আছে। আমাদের কাজ হলো একটি প্রোগ্রাম তৈরি করা যা ত্রিভুজে সর্বোচ্চ পথ যোগফল বের করবে।
উপাদানগুলো প্রথম সারিতে ১টি থেকে শুরু করে পরের সারিগুলোতে ক্রমবর্ধমান সংখ্যক উপাদান দিয়ে সাজানো থাকে, n-তম সারিতে nটি উপাদান থাকে।
প্রোগ্রামটি এমন পথটি খুঁজে বের করবে যা ত্রিভুজে সর্বোচ্চ উপাদান যোগফল দেবে।
সমস্যা বুঝতে নিচের উদাহরণটি দেখুন −
ইনপুট −
1 5 6 8 2 9
আউটপুট − 16
ব্যাখ্যা −
উপর থেকে নিচের দিকে যাওয়া পথটি সর্বোচ্চ যোগফল দেবে − 9+6+1 = 16
এই সমস্যা সমাধানের জন্য আমরা বটম-আপ পদ্ধতিতে ডাইনামিক প্রোগ্রামিং ব্যবহার করব।
এজন্য প্রথমে ত্রিভুজের সব সংখ্যাকে বাম দিকে সরিয়ে শেষে 0 দিয়ে পূরণ করব। এতে ত্রিভুজটি ন্যূনতম খরচ পথ সমস্যার মতো একটি ম্যাট্রিক্সের আকারে দেখাবে। এরপর আমরা নিচ থেকে শুরু করব, এবং প্রতিটি উপাদানের জন্য সমস্ত সম্ভাব্য পথ যাচাই করে সর্বোচ্চ যোগফল দেয় এমন পথটি বেছে নেব। এভipedia করে উপরে চলে আসব ত্রিভুজে সর্বোচ্চ পথ যোগফল বের করতে।
উদাহরণ
ত্রিভুজে সর্বোচ্চ পথ যোগফল বের করার প্রোগ্রাম −
#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
