इस समस्या में 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 अब हमारे लागत मैट्रिक्स का क्रम है क्योंकि अब हमारे पास एक निश्चित भाजक है। इसलिए, हमें अधिकतम पथ योग की गणना करने की आवश्यकता है। अब, यह क्लासिक dp समस्याओं में से एक है, और हम इसका उपयोग करके इसे हल करते हैं, और फिर हम अपना परिणाम प्रिंट करते हैं।
निष्कर्ष
इस ट्यूटोरियल में, हम अधिकतम औसत मान वाले पथ को खोजने के लिए एक समस्या का समाधान करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और संपूर्ण दृष्टिकोण (Normal) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। हमें उम्मीद है कि आपको यह ट्यूटोरियल मददगार लगा होगा।