Polku, jolla on suurin keskiarvo
Annettu neliömatriisi, jonka koko on N*N, jossa jokainen solu liittyy tiettyyn hintaan. Polku määritellään tietyksi solusarjaksi, joka alkaa ylävasemmasta solusta, liikkuu vain oikealle tai alas ja päättyy oikeaan alakulmaan. Haluamme löytää polun, jonka keskiarvo on suurin kaikista olemassa olevista poluista. Keskiarvo lasketaan jakamalla kokonaiskustannukset polulla vierailtujen solujen määrällä.
Esimerkkejä:
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
Yksi mielenkiintoinen havainto on, että ainoat sallitut liikkeet ovat alaspäin ja oikealle tarvitsemme N-1 alasliikettä ja N-1 oikeaa liikettä päästäksemme määränpäähän (oikealla alhaalla). Joten mikä tahansa polku vasemmasta yläkulmasta oikeaan alakulmaan vaatii 2N - 1 solua. sisään keskimäärin arvo, nimittäjä on kiinteä ja meidän on vain maksimoitava osoittaja. Siksi meidän on periaatteessa löydettävä maksimisummapolku. Polun maksimisumman laskeminen on klassinen dynaaminen ohjelmointiongelma, jos dp[i][j] edustaa maksimisummaa soluun (i j) alkaen (0 0), niin jokaisessa solussa (i j) päivitetään dp[i][j] alla olevan mukaisesti
for all i 1 <= i <= N
dp[i][0] = dp[i-1][0] + cost[i][0];
for all j 1 <= j <= N
dp[0][j] = dp[0][j-1] + cost[0][j];
otherwise
dp[i][j] = max(dp[i-1][j] dp[i][j-1]) + cost[i][j];
Kun saamme kaikkien polkujen maksimisumman, jaamme tämän summan (2N - 1) ja saamme maksimikeskiarvomme.
Toteutus:
C++Java//C/C++ program to find maximum average cost path #includeusing namespace std ; // Maximum number of rows and/or columns const int M = 100 ; // method returns maximum average of all path of // cost matrix double maxAverageOfPath ( int cost [ M ][ M ] int N ) { int dp [ N + 1 ][ N + 1 ]; dp [ 0 ][ 0 ] = cost [ 0 ][ 0 ]; /* Initialize first column of total cost(dp) array */ for ( int i = 1 ; i < N ; i ++ ) dp [ i ][ 0 ] = dp [ i -1 ][ 0 ] + cost [ i ][ 0 ]; /* Initialize first row of dp array */ for ( int j = 1 ; j < N ; j ++ ) dp [ 0 ][ j ] = dp [ 0 ][ j -1 ] + cost [ 0 ][ j ]; /* Construct rest of the dp array */ 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 ]; // divide maximum sum by constant path // length : (2N - 1) for getting average return ( double ) dp [ N -1 ][ N -1 ] / ( 2 * N -1 ); } /* Driver program to test above functions */ int main () { int cost [ M ][ M ] = { { 1 2 3 } { 6 5 4 } { 7 3 9 } }; printf ( '%f' maxAverageOfPath ( cost 3 )); return 0 ; } C#// JAVA Code for Path with maximum average // value import java.io.* ; class GFG { // method returns maximum average of all // path of cost matrix public static double maxAverageOfPath ( int cost [][] int N ) { int dp [][] = new int [ N + 1 ][ N + 1 ] ; dp [ 0 ][ 0 ] = cost [ 0 ][ 0 ] ; /* Initialize first column of total cost(dp) array */ for ( int i = 1 ; i < N ; i ++ ) dp [ i ][ 0 ] = dp [ i - 1 ][ 0 ] + cost [ i ][ 0 ] ; /* Initialize first row of dp array */ for ( int j = 1 ; j < N ; j ++ ) dp [ 0 ][ j ] = dp [ 0 ][ j - 1 ] + cost [ 0 ][ j ] ; /* Construct rest of the dp array */ for ( int i = 1 ; i < N ; i ++ ) for ( int j = 1 ; j < N ; j ++ ) dp [ i ][ j ] = Math . max ( dp [ i - 1 ][ j ] dp [ i ][ j - 1 ] ) + cost [ i ][ j ] ; // divide maximum sum by constant path // length : (2N - 1) for getting average return ( double ) dp [ N - 1 ][ N - 1 ] / ( 2 * N - 1 ); } /* Driver program to test above function */ public static void main ( String [] args ) { int cost [][] = {{ 1 2 3 } { 6 5 4 } { 7 3 9 }}; System . out . println ( maxAverageOfPath ( cost 3 )); } } // This code is contributed by Arnav Kr. Mandal.JavaScript// C# Code for Path with maximum average // value using System ; class GFG { // method returns maximum average of all // path of cost matrix public static double maxAverageOfPath ( int [] cost int N ) { int [] dp = new int [ N + 1 N + 1 ]; dp [ 0 0 ] = cost [ 0 0 ]; /* Initialize first column of total cost(dp) array */ for ( int i = 1 ; i < N ; i ++ ) dp [ i 0 ] = dp [ i - 1 0 ] + cost [ i 0 ]; /* Initialize first row of dp array */ for ( int j = 1 ; j < N ; j ++ ) dp [ 0 j ] = dp [ 0 j - 1 ] + cost [ 0 j ]; /* Construct rest of the dp array */ for ( int i = 1 ; i < N ; i ++ ) for ( int j = 1 ; j < N ; j ++ ) dp [ i j ] = Math . Max ( dp [ i - 1 j ] dp [ i j - 1 ]) + cost [ i j ]; // divide maximum sum by constant path // length : (2N - 1) for getting average return ( double ) dp [ N - 1 N - 1 ] / ( 2 * N - 1 ); } // Driver Code public static void Main () { int [] cost = {{ 1 2 3 } { 6 5 4 } { 7 3 9 }}; Console . Write ( maxAverageOfPath ( cost 3 )); } } // This code is contributed by nitin mittal.PHP< script > // JavaScript Code for Path with maximum average value // method returns maximum average of all // path of cost matrix function maxAverageOfPath ( cost N ) { let dp = new Array ( N + 1 ); for ( let i = 0 ; i < N + 1 ; i ++ ) { dp [ i ] = new Array ( N + 1 ); for ( let j = 0 ; j < N + 1 ; j ++ ) { dp [ i ][ j ] = 0 ; } } dp [ 0 ][ 0 ] = cost [ 0 ][ 0 ]; /* Initialize first column of total cost(dp) array */ for ( let i = 1 ; i < N ; i ++ ) dp [ i ][ 0 ] = dp [ i - 1 ][ 0 ] + cost [ i ][ 0 ]; /* Initialize first row of dp array */ for ( let j = 1 ; j < N ; j ++ ) dp [ 0 ][ j ] = dp [ 0 ][ j - 1 ] + cost [ 0 ][ j ]; /* Construct rest of the dp array */ for ( let i = 1 ; i < N ; i ++ ) for ( let j = 1 ; j < N ; j ++ ) dp [ i ][ j ] = Math . max ( dp [ i - 1 ][ j ] dp [ i ][ j - 1 ]) + cost [ i ][ j ]; // divide maximum sum by constant path // length : (2N - 1) for getting average return dp [ N - 1 ][ N - 1 ] / ( 2 * N - 1 ); } let cost = [[ 1 2 3 ] [ 6 5 4 ] [ 7 3 9 ]]; document . write ( maxAverageOfPath ( cost 3 )); < /script>Python3// Php program to find maximum average cost path // method returns maximum average of all path of // cost matrix function maxAverageOfPath ( $cost $N ) { $dp = array ( array ()) ; $dp [ 0 ][ 0 ] = $cost [ 0 ][ 0 ]; /* Initialize first column of total cost(dp) array */ for ( $i = 1 ; $i < $N ; $i ++ ) $dp [ $i ][ 0 ] = $dp [ $i - 1 ][ 0 ] + $cost [ $i ][ 0 ]; /* Initialize first row of dp array */ for ( $j = 1 ; $j < $N ; $j ++ ) $dp [ 0 ][ $j ] = $dp [ 0 ][ $j - 1 ] + $cost [ 0 ][ $j ]; /* Construct rest of the dp array */ for ( $i = 1 ; $i < $N ; $i ++ ) { for ( $j = 1 ; $j <= $N ; $j ++ ) $dp [ $i ][ $j ] = max ( $dp [ $i - 1 ][ $j ] $dp [ $i ][ $j - 1 ]) + $cost [ $i ][ $j ]; } // divide maximum sum by constant path // length : (2N - 1) for getting average return $dp [ $N - 1 ][ $N - 1 ] / ( 2 * $N - 1 ); } // Driver code $cost = array ( array ( 1 2 3 ) array ( 6 5 4 ) array ( 7 3 9 ) ) ; echo maxAverageOfPath ( $cost 3 ) ; // This code is contributed by Ryuga ?>
Lähtö5.200000Aika monimutkaisuus : O(N 2 ) tietylle syötteelle N
Aputila: O(N 2 ) annetulle tulolle N.Tapa - 2: Käyttämättä ylimääräistä N*N tilaa
Voimme käyttää syöttökustannustaulukkoa dp:nä ans:n tallentamiseen. joten tällä tavalla emme tarvitse ylimääräistä dp-taulukkoa tai ei ylimääräistä tilaa.
Yksi havainto on, että ainoat sallitut liikkeet ovat alaspäin ja oikealle tarvitsemme N-1 alasliikettä ja N-1 oikeaa liikettä päästäksemme määränpäähän (oikealla alhaalla). Joten mikä tahansa polku vasemmasta yläkulmasta oikeaan alakulmaan vaatii 2N - 1 solua. sisään keskimäärin arvo, nimittäjä on kiinteä ja meidän on vain maksimoitava osoittaja. Siksi meidän on periaatteessa löydettävä maksimisummapolku. Polun maksimisumman laskeminen on klassinen dynaamisen ohjelmoinnin ongelma, eikä dp[i][j]:n laskemisen jälkeen tarvita aiempaa kustannus[i][j]-arvoa, jotta voimme muokata kustannus[i][j]-arvoa siten, että emme tarvitse ylimääräistä tilaa dp[i][j]:lle.
for all i 1 <= i < N
cost[i][0] = cost[i-1][0] + cost[i][0];
for all j 1 <= j < N
cost[0][j] = cost[0][j-1] + cost[0][j];
otherwise
cost[i][j] = max(cost[i-1][j] cost[i][j-1]) + cost[i][j];
Alla on yllä olevan lähestymistavan toteutus:
C++Java// C++ program to find maximum average cost path #includeusing namespace std ; // Method returns maximum average of all path of cost matrix double maxAverageOfPath ( vector < vector < int >> cost ) { int N = cost . size (); // Initialize first column of total cost array for ( int i = 1 ; i < N ; i ++ ) cost [ i ][ 0 ] = cost [ i ][ 0 ] + cost [ i - 1 ][ 0 ]; // Initialize first row of array for ( int j = 1 ; j < N ; j ++ ) cost [ 0 ][ j ] = cost [ 0 ][ j - 1 ] + cost [ 0 ][ j ]; // Construct rest of the array for ( int i = 1 ; i < N ; i ++ ) for ( int j = 1 ; j <= N ; j ++ ) cost [ i ][ j ] = max ( cost [ i - 1 ][ j ] cost [ i ][ j - 1 ]) + cost [ i ][ j ]; // divide maximum sum by constant path // length : (2N - 1) for getting average return ( double ) cost [ N - 1 ][ N - 1 ] / ( 2 * N - 1 ); } // Driver program int main () { vector < vector < int >> cost = {{ 1 2 3 } { 6 5 4 } { 7 3 9 } }; cout < < maxAverageOfPath ( cost ); return 0 ; } C#// Java program to find maximum average cost path import java.io.* ; class GFG { // Method returns maximum average of all path of cost // matrix static double maxAverageOfPath ( int [][] cost ) { int N = cost . length ; // Initialize first column of total cost array for ( int i = 1 ; i < N ; i ++ ) cost [ i ][ 0 ] = cost [ i ][ 0 ] + cost [ i - 1 ][ 0 ] ; // Initialize first row of array for ( int j = 1 ; j < N ; j ++ ) cost [ 0 ][ j ] = cost [ 0 ][ j - 1 ] + cost [ 0 ][ j ] ; // Construct rest of the array for ( int i = 1 ; i < N ; i ++ ) for ( int j = 1 ; j < N ; j ++ ) cost [ i ][ j ] = Math . max ( cost [ i - 1 ][ j ] cost [ i ][ j - 1 ] ) + cost [ i ][ j ] ; // divide maximum sum by constant path // length : (2N - 1) for getting average return ( double ) cost [ N - 1 ][ N - 1 ] / ( 2 * N - 1 ); } // Driver program public static void main ( String [] args ) { int [][] cost = { { 1 2 3 } { 6 5 4 } { 7 3 9 } }; System . out . println ( maxAverageOfPath ( cost )); } } // This code is contributed by karandeep1234JavaScript// C# program to find maximum average cost path using System ; class GFG { // Method returns maximum average of all path of cost // matrix static double maxAverageOfPath ( int [ ] cost ) { int N = cost . GetLength ( 0 ); // Initialize first column of total cost array for ( int i = 1 ; i < N ; i ++ ) cost [ i 0 ] = cost [ i 0 ] + cost [ i - 1 0 ]; // Initialize first row of array for ( int j = 1 ; j < N ; j ++ ) cost [ 0 j ] = cost [ 0 j - 1 ] + cost [ 0 j ]; // Construct rest of the array for ( int i = 1 ; i < N ; i ++ ) for ( int j = 1 ; j < N ; j ++ ) cost [ i j ] = Math . Max ( cost [ i - 1 j ] cost [ i j - 1 ]) + cost [ i j ]; // divide maximum sum by constant path // length : (2N - 1) for getting average return ( double ) cost [ N - 1 N - 1 ] / ( 2 * N - 1 ); } // Driver program static void Main ( string [] args ) { int [ ] cost = { { 1 2 3 } { 6 5 4 } { 7 3 9 } }; Console . WriteLine ( maxAverageOfPath ( cost )); } } // This code is contributed by karandeep1234Python3// Method returns maximum average of all path of cost matrix function maxAverageOfPath ( cost ) { let N = cost . length ; // Initialize first column of total cost array for ( let i = 1 ; i < N ; i ++ ) cost [ i ][ 0 ] = cost [ i ][ 0 ] + cost [ i - 1 ][ 0 ]; // Initialize first row of array for ( let j = 1 ; j < N ; j ++ ) cost [ 0 ][ j ] = cost [ 0 ][ j - 1 ] + cost [ 0 ][ j ]; // Construct rest of the array for ( let i = 1 ; i < N ; i ++ ) for ( let j = 1 ; j <= N ; j ++ ) cost [ i ][ j ] = Math . max ( cost [ i - 1 ][ j ] cost [ i ][ j - 1 ]) + cost [ i ][ j ]; // divide maximum sum by constant path // length : (2N - 1) for getting average return ( cost [ N - 1 ][ N - 1 ]) / ( 2.0 * N - 1 ); } // Driver program let cost = [[ 1 2 3 ] [ 6 5 4 ] [ 7 3 9 ]]; console . log ( maxAverageOfPath ( cost )) // This code is contributed by karandeep1234.
Lähtö5.2Aika monimutkaisuus: O(N*N)
Aputila: O(1)
