최대 평균값이 있는 경로
각 셀이 특정 비용과 연관되어 있는 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]가 (0 0)에서 셀(i j)까지의 최대 합을 나타내고 각 셀(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++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 ?>
산출5.200000시간 복잡도 : 에 2 ) 주어진 입력 N에 대해
보조 공간: 에 2 ) 주어진 입력 N에 대해.방법 - 2: 추가 N*N 공간을 사용하지 않음
입력 비용 배열을 dp로 사용하여 ans를 저장할 수 있습니다. 이렇게 하면 추가 dp 배열이나 추가 공간이 필요하지 않습니다.
한 가지 관찰은 허용되는 유일한 이동은 아래쪽과 오른쪽이라는 것입니다. 목적지(가장 오른쪽 아래)에 도달하려면 N-1번의 아래쪽 이동과 N-1번의 오른쪽 이동이 필요합니다. 따라서 왼쪽 상단에서 오른쪽 하단까지의 모든 경로에는 2N - 1 셀이 필요합니다. ~ 안에 평균 분모는 고정되어 있으므로 분자를 최대화하면 됩니다. 따라서 기본적으로 최대 합 경로를 찾아야 합니다. 경로의 최대 합을 계산하는 것은 고전적인 동적 프로그래밍 문제입니다. 또한 dp[i][j]를 계산한 후에는 이전 비용[i][j] 값이 필요하지 않으므로 dp[i][j]에 대한 추가 공간이 필요하지 않도록 비용[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++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.
산출5.2시간 복잡도: O(N*N)
보조 공간: 오(1)
