Donada una matriu quadrada de mida N*N on cada cel·la està associada a un cost específic. Un camí es defineix com una seqüència específica de cel·les que comença des de la cel·la superior esquerra es mou només cap a la dreta o cap avall i acaba a la cel·la inferior dreta. Volem trobar un camí amb la mitjana màxima de tots els camins existents. La mitjana es calcula com a cost total dividit pel nombre de cel·les visitades al camí.
Exemples:
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
Una observació interessant és que els únics moviments permesos són cap avall i a la dreta necessitem N-1 moviments cap avall i N-1 moviments a la dreta per arribar a la destinació (a la part inferior dreta). Per tant, qualsevol camí des de la cantonada superior esquerra fins a la cantonada inferior dreta requereix 2N - 1 cel·les. En mitjana el valor del denominador és fix i només hem de maximitzar el numerador. Per tant, bàsicament hem de trobar el camí de la suma màxima. El càlcul de la suma màxima del camí és un problema clàssic de programació dinàmica si dp[i][j] representa la suma màxima fins a la cel·la (i j) de (0 0), aleshores a cada cel·la (i j) actualitzem dp[i][j] com a continuació
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];
Un cop aconseguim la suma màxima de tots els camins, dividirem aquesta suma per (2N - 1) i obtindrem la nostra mitjana màxima.
Implementació:
C++//C/C++ program to find maximum average cost path #include
// 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.
// 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+1N+1]; dp[00] = cost[00]; /* Initialize first column of total cost(dp) array */ for (int i = 1; i < N; i++) dp[i 0] = dp[i - 10] + cost[i 0]; /* Initialize first row of dp array */ for (int j = 1; j < N; j++) dp[0 j] = dp[0j - 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[ij - 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.
<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>
// 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 ?> # Python program to find # maximum average cost path # Maximum number of rows # and/or columns M = 100 # method returns maximum average of # all path of cost matrix def maxAverageOfPath(cost N): dp = [[0 for i in range(N + 1)] for j in range(N + 1)] dp[0][0] = cost[0][0] # Initialize first column of total cost(dp) array for i in range(1 N): dp[i][0] = dp[i - 1][0] + cost[i][0] # Initialize first row of dp array for j in range(1 N): dp[0][j] = dp[0][j - 1] + cost[0][j] # Construct rest of the dp array for i in range(1 N): for j in range(1 N): 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 program to test above function cost = [[1 2 3] [6 5 4] [7 3 9]] print(maxAverageOfPath(cost 3)) # This code is contributed by Soumen Ghosh.
Sortida
5.200000
Complexitat temporal : O(N2) per a l'entrada N donada
Espai auxiliar: O(N2) per a l'entrada donada N.
Mètode - 2: sense utilitzar espai N*N addicional
Podem utilitzar la matriu de costos d'entrada com a dp per emmagatzemar l'ans. així que d'aquesta manera no necessitem una matriu dp addicional ni aquest espai addicional.
Una observació és que els únics moviments permesos són cap avall i cap a la dreta necessitem N-1 moviments cap avall i N-1 moviments cap a la dreta per arribar a la destinació (a la part inferior dreta). Per tant, qualsevol camí des de la cantonada superior esquerra fins a la cantonada inferior dreta requereix 2N - 1 cel·la. En mitjana el valor del denominador és fix i només hem de maximitzar el numerador. Per tant, bàsicament hem de trobar el camí de la suma màxima. Calcular la suma màxima del camí és un problema clàssic de programació dinàmica, a més, no necessitem cap valor de cost anterior [i][j] després de calcular dp[i][j], de manera que podem modificar el valor de cost[i][j] de manera que no necessitem espai addicional per a dp[i][j].
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];
A continuació es mostra la implementació de l'enfocament anterior:
C++// C++ program to find maximum average cost path #include
// 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 karandeep1234
// 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 karandeep1234
// 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.
# Python program to find maximum average cost path from typing import List def maxAverageOfPath(cost: List[List[int]]) -> float: N = len(cost) # Initialize first column of total cost array for i in range(1 N): cost[i][0] = cost[i][0] + cost[i - 1][0] # Initialize first row of array for j in range(1 N): cost[0][j] = cost[0][j - 1] + cost[0][j] # Construct rest of the array for i in range(1 N): for j in range(1 N): 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 cost[N - 1][N - 1] / (2 * N - 1) # Driver program def main(): cost = [[1 2 3] [6 5 4] [7 3 9]] print(maxAverageOfPath(cost)) if __name__ == '__main__': main()
Sortida
5.2
Complexitat temporal: O(N*N)
Espai auxiliar: O(1)