平均値が最大のパス
各セルが特定のコストに関連付けられている、サイズ 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
興味深い観察の 1 つは、許可される移動は下と右のみであるということです。目的地 (右下) に到達するには、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: Extra N*N スペースを使用しない
入力コスト配列を dp として使用して、ans を保存できます。したがって、この方法では、余分な dp 配列や余分なスペースは必要ありません。
観察の 1 つは、許可される移動は下と右のみであるということです。目的地 (右下) に到達するには、N-1 回の下への移動と N-1 回の右への移動が必要です。したがって、左上隅から右下隅までのパスには 2N - 1 セルが必要です。で 平均 値の分母は固定されているため、分子を最大化するだけで済みます。したがって、基本的には最大合計パスを見つける必要があります。パスの最大合計を計算するのは古典的な動的プログラミングの問題です。また、dp[i][j] を計算した後に prevcost[i][j] の値は必要ないので、dp[i][j] に余分なスペースが必要ないようにcost[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)
