Maximize path sum from top | Function to get the maximum path sum from top - left cell to all other cells of the given matrix ; Store the maximum path sum Initialize the value of dp [ i ] [ j ] to 0. ; Base case ; Compute the value of dp [ i ] [ j ] using the recurrence relation ; Print maximum path sum from the top - left cell ; Driver code
def pathSum ( mat , N , M ) : NEW_LINE INDENT dp = [ [ 0 for x in range ( M ) ] for y in range ( N ) ] NEW_LINE dp [ 0 ] [ 0 ] = mat [ 0 ] [ 0 ] NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT dp [ i ] [ 0 ] = ( mat [ i ] [ 0 ] + dp [ i - 1 ] [ 0 ] ) NEW_LINE DEDENT for j in range ( 1 , M ) : NEW_LINE INDENT dp [ 0 ] [ j ] = ( mat [ 0 ] [ j ] + dp [ 0 ] [ j - 1 ] ) NEW_LINE DEDENT for i in range ( 1 , N ) : NEW_LINE INDENT for j in range ( 1 , M ) : NEW_LINE INDENT dp [ i ] [ j ] = ( mat [ i ] [ j ] + max ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) ) NEW_LINE DEDENT DEDENT for i in range ( N ) : NEW_LINE INDENT for j in range ( M ) : NEW_LINE INDENT print ( dp [ i ] [ j ] , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT mat = [ [ 3 , 2 , 1 ] , [ 6 , 5 , 4 ] , [ 7 , 8 , 9 ] ] NEW_LINE N = 3 NEW_LINE M = 3 NEW_LINE pathSum ( mat , N , M ) NEW_LINE DEDENT