এই সমস্যায় একটি ২D ম্যাট্রিক্স দেওয়া আছে এবং আমাদের সর্বোচ্চ গড় মান (maximum average value) رکھা পথ বের করতে হবে। পথের শুরু হবে উপরের বাম কোণার সেল (top-left) এবং শেষ হবে নিচের ডান কোণার সেল (bottom-right)। উদাহরণ −
ইনপুট: Matrix = [1, 2, 3; 4, 5, 6; 7, 8, 9] আউটপুট: 5.8 সর্বোচ্চ গড় মান barne পথ: 1 → 4 → 7 → 8 → 9 পথের যোগফল = 29, গড় = 29/5 = 5.8
এই সমস্যাতেই আমরা শুধু ডান বা নিচে যেতে পারি। এতে সমস্যা সহজ হয় কারণ আমরা জানি ডেস্টিনেশন পৌঁছাতে (N-1) বার ডান এবং (N-1) বার নিচে যেতে হবে। এটি শর্টেস্ট ভ্যালিড পথ, তাই আমরা এই পর্যবেক্ষণ দিয়ে আমাদের পদ্ধতি তৈরি করব।
এই পদ্ধতিতে, আমরা ডাইনামিক প্রোগ্রামিং (Dynamic Programming) প্রয়োগ করব সর্বোচ্চ পথের যোগফল (maximum path sum) বের করতে, কারণ হর (denominator) ফিক্সড।
উপরোক্ত পদ্ধতির C++ কোড
#include <bits/stdc++.h> using namespace std; int maximumPathSum(int cost[][3], int n){ // সর্বোচ্চ গড় ফেরানোর ফাংশন int dp[n+1][n+1]; dp[0][0] = cost[0][0]; for (int i = 1; i < n; i++) // dp ম্যাট্রিক্সের প্রথম কলাম ইনিশিয়ালাইজ dp[i][0] = dp[i-1][0] + cost[i][0]; for (int j = 1; j < n; j++) // dp ম্যাট্রিক্সের প্রথম রো ইনিশিয়ালাইজ dp[0][j] = dp[0][j-1] + cost[0][j]; for (int i = 1; i < n; i++) // বাকি ম্যাট্রিক্স কনস্ট্রাক্ট for (int j = 1; j <= n; j++) dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + cost[i][j]; return dp[n-1][n-1]; // সর্বোচ্চ পথ যোগফল ফেরত, ধরে ভাগ করব } int main(){ int cost[3][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }; // দেওয়া গ্রিড int n = 3; // ম্যাট্রিক্স অর্ডার printf("%.1f", float(maximumPathSum(cost, n)) / float((2*n-1))); return 0; }
5.8
উপরের পদ্ধতিতে, আমরা পর্যবেক্ষণ করেছি যে সর্বোচ্চ মুভ সংখ্যা = (2×n) - 1, যেখানে n হলো কাস্ট ম্যাট্রিক্সের অর্ডার। যেহেতু হর ফিক্সড, তাই আমাদের সর্বোচ্চ পথের যোগফল বের করতে হবে। এটি একটি ক্লাসিক DP সমস্যা, আমরা DP দিয়ে সমাধান করেছি এবং ফলাফল প্রিন্ট করেছি।
এই টিউটোরিয়ালে আমরা সর্বোচ্চ গড় মান barne পথ বের করার সমস্যা সমাধান করেছি। আমরা এই সমস্যার C++ প্রোগ্রাম ও সম্পূর্ণ পদ্ধতি দেখেছি। একই প্রোগ্রাম C, Java, Python ইত্যাদি ভাষায়ও লিখা যায়। আশা করি আপনি এই টিউটোরিয়ালটি সহায়ক পাবেন।
