এই সমস্যায় একটি 2 ডি ম্যাট্রিক্স দেওয়া হয়েছে, এবং আমাদের সর্বাধিক গড় মান থাকা পাথগুলি খুঁজে বের করতে হবে। পথের জন্য, আমাদের উৎস হল উপরের বাম কক্ষ, এবং গন্তব্য হল নীচের ডানদিকের কক্ষ, উদাহরণস্বরূপ −
Input : Matrix = [1, 2, 3 4, 5, 6 7, 8, 9] Output : 5.8 Path with maximum average is, 1 -> 4 -> 7 -> 8 -> 9 Sum of the path is 29 and average is 29/5 = 5.8
এই সমস্যায়, আমাদের কেবল ডানে বা নীচের দিকে যেতে দেওয়া হয়। এটি আমাদের সমস্যাকে আরও সহজ করে তোলে কারণ আমরা জানি যে আমাদের ডানদিকে যেতে N-1 প্রয়োজন এবং N-1 আমাদের গন্তব্যে পৌঁছানোর জন্য নিচে চলে যায়। এটি হল সংক্ষিপ্ততম বৈধ পথ, যাতে আমরা এই পর্যবেক্ষণগুলির মাধ্যমে আমাদের পদ্ধতির বিকাশ করব৷
৷সমাধান খোঁজার পদ্ধতি
এই পদ্ধতিতে, হর স্থির হওয়ার সাথে সাথে সর্বাধিক পাথ যোগফল গণনা করতে আমাদের গতিশীল প্রোগ্রামিং প্রয়োগ করতে হবে।
উদাহরণ
উপরের পদ্ধতির জন্য C++ কোড
#include <bits/stdc++.h>
using namespace std;
int maximumPathSum(int cost[][3], int n){ // our function that return maximum average
int dp[n+1][n+1];
dp[0][0] = cost[0][0];
for (int i = 1; i < n; i++) // initializing the first column of our dp matrix
dp[i][0] = dp[i-1][0] + cost[i][0];
for (int j = 1; j < n; j++) // initializing the first row of our dp matrix
dp[0][j] = dp[0][j-1] + cost[0][j];
for (int i = 1; i < n; i++) // constructing the rest of our matrix
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]; // now we divide the maximum path sum with the number of moves
}
int main(){
int cost[3][3] = { {1, 2, 3}, {4, 5, 6},{7, 8, 9}};// given grid
int n = 3; // order of our matrix
printf("%.1f", float(maximumPathSum(cost, n)) / float((2*n-1)));
return 0;
} আউটপুট
5.8
উপরের কোডের ব্যাখ্যা
উপরের পদ্ধতিতে, আমরা লক্ষ্য করেছি যে আমরা যে সর্বাধিক চালগুলি নিই তা সমান (2*n) - 1, যেখানে n হল আমাদের খরচ ম্যাট্রিক্সের ক্রম যেহেতু এখন আমাদের একটি নির্দিষ্ট হর রয়েছে। সুতরাং, আমাদের সর্বাধিক পাথ যোগফল গণনা করতে হবে। এখন, এটি ক্লাসিক ডিপি সমস্যাগুলির মধ্যে একটি, এবং আমরা এটি ব্যবহার করে এটি সমাধান করি, এবং তারপর আমরা আমাদের ফলাফল প্রিন্ট করি৷
উপসংহার
এই টিউটোরিয়ালে, আমরা সর্বাধিক গড় মান সহ পথ খুঁজে পেতে একটি সমস্যার সমাধান করি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই টিউটোরিয়ালটি সহায়ক হবে৷
