Path with maximum average value | Maximum number of rows and / or columns ; method returns maximum average of all path of cost matrix ; Initialize first column of total cost ( dp ) array ; Initialize first row of dp array ; Construct rest of the dp array ; divide maximum sum by constant path length : ( 2 N - 1 ) for getting average ; Driver program to test above function
M = 100 NEW_LINE def maxAverageOfPath ( cost , N ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( N + 1 ) ] for j in range ( N + 1 ) ] NEW_LINE dp [ 0 ] [ 0 ] = cost [ 0 ] [ 0 ] NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT dp [ i ] [ 0 ] = dp [ i - 1 ] [ 0 ] + cost [ i ] [ 0 ] NEW_LINE DEDENT for j in range ( 1 , N ) : NEW_LINE INDENT dp [ 0 ] [ j ] = dp [ 0 ] [ j - 1 ] + cost [ 0 ] [ j ] NEW_LINE DEDENT for i in range ( 1 , N ) : NEW_LINE INDENT for j in range ( 1 , N ) : NEW_LINE INDENT dp [ i ] [ j ] = max ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) + cost [ i ] [ j ] NEW_LINE DEDENT DEDENT return dp [ N - 1 ] [ N - 1 ] / ( 2 * N - 1 ) NEW_LINE DEDENT cost = [ [ 1 , 2 , 3 ] , [ 6 , 5 , 4 ] , [ 7 , 3 , 9 ] ] NEW_LINE print ( maxAverageOfPath ( cost , 3 ) ) NEW_LINE