human
Paths from entry to exit in matrix and maximum path sum | Recursive function to return the total paths from grid [ i ] [ j ] to grid [ n - 1 ] [ n - 1 ].
Out of bounds.
If the current state hasn 't been solved before .
Only valid move is right.
Only valid move is down.
Right and down , both are valid moves.
Recursive function to return the maximum sum along the path from grid [ i , j ] to grid [ n - 1 , n - 1 ].
Out of bounds.
If the current state hasn 't been solved before .
Only valid move is right.
Only valid move is down.
Right and down , both are valid moves.
Driver code.
Fill the dp [ n ] [ n ] array with - 1.
When source and destination are same then there is only 1 path.
Print the count of paths from grid [ 0 , 0 ] to grid [ n - 1 ] [ n - 1 ].
Fill the dp [ n ] [ n ] array again with - 1.
When source and destination are same then the sum is grid [ n - 1 ] [ n - 1 ].
Print the maximum sum among all the paths from grid [ 0 , 0 ] to grid [ n - 1 ] [ n - 1 ]"
How can the above be solved in Python?
assistant
#Here is code to paths from entry to exit in matrix and maximum path sum and the other steps required.
 def totalPaths ( i , j , n , grid , dp ) :
	if ( i < 0 or j < 0 or i >= n or j >= n ) :
		return 0
	if ( dp [ i ] [ j ] == - 1 ) :
		if ( grid [ i ] [ j ] == 1 ) :
			dp [ i ] [ j ] = totalPaths ( i , j + 1 , n , grid , dp )
		elif ( grid [ i ] [ j ] == 2 ) :
			dp [ i ] [ j ] = totalPaths ( i + 1 , j , n , grid , dp )
		else :
			dp [ i ] [ j ] = totalPaths ( i , j + 1 , n , grid , dp ) + totalPaths ( i + 1 , j , n , grid , dp )
	return dp [ i ] [ j ]
def maxSumPath ( i , j , n , grid , dp ) :
	if ( i < 0 or j < 0 or i >= n or j >= n ) :
		return 0
	if ( dp [ i ] [ j ] == - 1 ) :
		if ( grid [ i ] [ j ] == 1 ) :
			dp [ i ] [ j ] = grid [ i ] [ j ] + maxSumPath ( i , j + 1 , n , grid , dp )
		elif ( grid [ i ] [ j ] == 2 ) :
			dp [ i ] [ j ] = grid [ i ] [ j ] + maxSumPath ( i + 1 , j , n , grid , dp )
		else :
			dp [ i ] [ j ] = grid [ i ] [ j ] + max ( maxSumPath ( i , j + 1 , n , grid , dp ) , maxSumPath ( i + 1 , j , n , grid , dp ) )
	return dp [ i ] [ j ]
if __name__ == ' _ _ main _ _ ' :
	grid = [ [ 1 , 1 , 3 , 2 , 1 ] , [ 3 , 2 , 2 , 1 , 2 ] , [ 1 , 3 , 3 , 1 , 3 ] , [ 1 , 2 , 3 , 1 , 2 ] , [ 1 , 1 , 1 , 3 , 1 ] ]
	n = len ( grid [ 0 ] )
	dp = [ [ - 1 ] * n ] * n
	dp [ n - 1 ] [ n - 1 ] = 1
	print ( " Total ▁ paths : " , totalPaths ( 0 , 0 , n , grid , dp ) )
	dp = [ [ - 1 ] * n ] * n
	dp [ n - 1 ] [ n - 1 ] = grid [ n - 1 ] [ n - 1 ]
	print ( " Maximum ▁ sum : " , maxSumPath ( 0 , 0 , n , grid , dp ) )