Дадена е квадратна матрица с размер N*N, където всяка клетка е свързана с конкретна цена. Пътеката се дефинира като специфична последователност от клетки, която започва от горната лява клетка и се движи само надясно или надолу и завършва в долната дясна клетка. Искаме да намерим път с максимална средна стойност за всички съществуващи пътища. Средната стойност се изчислява като общата цена, разделена на броя клетки, посетени в пътя.
Примери:
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 движения надясно, за да достигнем дестинацията (най-долу вдясно). Така че всеки път от горния ляв ъгъл до долния десен ъгъл изисква 2N - 1 клетки. в средно стойност знаменателят е фиксиран и трябва просто да увеличим числителя. Следователно ние основно трябва да намерим пътя на максималната сума. Изчисляването на максималната сума на пътя е класически проблем за динамично програмиране, ако dp[i][j] представлява максимална сума до клетка (i j) от (0 0), тогава във всяка клетка (i j) актуализираме dp[i][j] както е показано по-долу
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];
След като получим максималната сума от всички пътища, ще разделим тази сума на (2N - 1) и ще получим нашата максимална средна стойност.
Изпълнение:
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.
Изход
5.200000
Времева сложност : O(N2) за даден вход N
Помощно пространство: O(N2) за даден вход N.
Метод - 2: Без използване на допълнително N*N пространство
Можем да използваме масив от входни разходи като dp за съхраняване на ans. така че по този начин нямаме нужда от допълнителен dp масив или никакво допълнително пространство.
Едно наблюдение е, че единствените разрешени движения са надолу и надясно, имаме нужда от N-1 движения надолу и N-1 движения надясно, за да достигнем дестинацията (най-долу вдясно). Така че всеки път от горния ляв ъгъл до долния десен ъгъл изисква 2N - 1 клетка. в средно стойност знаменателят е фиксиран и трябва просто да увеличим числителя. Следователно ние основно трябва да намерим пътя на максималната сума. Изчисляването на максималната сума на пътя е класически проблем за динамично програмиране, също така не се нуждаем от предишна стойност на cost[i][j] след изчисляване на dp[i][j], така че можем да модифицираме стойността на cost[i][j] така, че да не се нуждаем от допълнително място за 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];
По-долу е изпълнението на горния подход:
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()
Изход
5.2
Времева сложност: O(N*N)
Помощно пространство: О(1)