Maximum sum path in a matrix from top to bottom and back | Python 3 implementation of the approach ; Input matrix ; DP matrix ; Function to return the sum of the cells arr [ i1 ] [ j1 ] and arr [ i2 ] [ j2 ] ; Recursive function to return the required maximum cost path ; Column number of second path ; Base Case ; If already calculated , return from DP matrix ; Recurring for neighbouring cells of both paths together ; Saving result to the DP matrix for current state ; Driver code ; set initial value
import sys NEW_LINE n = 4 NEW_LINE m = 4 NEW_LINE arr = [ [ 1 , 0 , 3 , - 1 ] , [ 3 , 5 , 1 , - 2 ] , [ - 2 , 0 , 1 , 1 ] , [ 2 , 1 , - 1 , 1 ] ] NEW_LINE cache = [ [ [ - 1 for i in range ( 5 ) ] for j in range ( 5 ) ] for k in range ( 5 ) ] NEW_LINE def sum ( i1 , j1 , i2 , j2 ) : NEW_LINE INDENT if ( i1 == i2 and j1 == j2 ) : NEW_LINE INDENT return arr [ i1 ] [ j1 ] NEW_LINE DEDENT return arr [ i1 ] [ j1 ] + arr [ i2 ] [ j2 ] NEW_LINE DEDENT def maxSumPath ( i1 , j1 , i2 ) : NEW_LINE INDENT j2 = i1 + j1 - i2 NEW_LINE if ( i1 >= n or i2 >= n or j1 >= m or j2 >= m ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( cache [ i1 ] [ j1 ] [ i2 ] != - 1 ) : NEW_LINE INDENT return cache [ i1 ] [ j1 ] [ i2 ] NEW_LINE DEDENT ans = - sys . maxsize - 1 NEW_LINE ans = max ( ans , maxSumPath ( i1 + 1 , j1 , i2 + 1 ) + sum ( i1 , j1 , i2 , j2 ) ) NEW_LINE ans = max ( ans , maxSumPath ( i1 , j1 + 1 , i2 ) + sum ( i1 , j1 , i2 , j2 ) ) NEW_LINE ans = max ( ans , maxSumPath ( i1 , j1 + 1 , i2 + 1 ) + sum ( i1 , j1 , i2 , j2 ) ) NEW_LINE ans = max ( ans , maxSumPath ( i1 + 1 , j1 , i2 ) + sum ( i1 , j1 , i2 , j2 ) ) NEW_LINE cache [ i1 ] [ j1 ] [ i2 ] = ans NEW_LINE return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT print ( maxSumPath ( 0 , 0 , 0 ) ) NEW_LINE DEDENT