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 ]
def totalPaths ( i , j , n , grid , dp ) : NEW_LINE INDENT if ( i < 0 or j < 0 or i >= n or j >= n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ i ] [ j ] == - 1 ) : NEW_LINE INDENT if ( grid [ i ] [ j ] == 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = totalPaths ( i , j + 1 , n , grid , dp ) NEW_LINE DEDENT elif ( grid [ i ] [ j ] == 2 ) : NEW_LINE INDENT dp [ i ] [ j ] = totalPaths ( i + 1 , j , n , grid , dp ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = totalPaths ( i , j + 1 , n , grid , dp ) + totalPaths ( i + 1 , j , n , grid , dp ) NEW_LINE DEDENT DEDENT return dp [ i ] [ j ] NEW_LINE DEDENT def maxSumPath ( i , j , n , grid , dp ) : NEW_LINE INDENT if ( i < 0 or j < 0 or i >= n or j >= n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ i ] [ j ] == - 1 ) : NEW_LINE INDENT if ( grid [ i ] [ j ] == 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = grid [ i ] [ j ] + maxSumPath ( i , j + 1 , n , grid , dp ) NEW_LINE DEDENT elif ( grid [ i ] [ j ] == 2 ) : NEW_LINE INDENT dp [ i ] [ j ] = grid [ i ] [ j ] + maxSumPath ( i + 1 , j , n , grid , dp ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = grid [ i ] [ j ] + max ( maxSumPath ( i , j + 1 , n , grid , dp ) , maxSumPath ( i + 1 , j , n , grid , dp ) ) NEW_LINE DEDENT DEDENT return dp [ i ] [ j ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT 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 ] ] NEW_LINE n = len ( grid [ 0 ] ) NEW_LINE dp = [ [ - 1 ] * n ] * n NEW_LINE dp [ n - 1 ] [ n - 1 ] = 1 NEW_LINE print ( " Total ▁ paths : " , totalPaths ( 0 , 0 , n , grid , dp ) ) NEW_LINE dp = [ [ - 1 ] * n ] * n NEW_LINE dp [ n - 1 ] [ n - 1 ] = grid [ n - 1 ] [ n - 1 ] NEW_LINE print ( " Maximum ▁ sum : " , maxSumPath ( 0 , 0 , n , grid , dp ) ) NEW_LINE DEDENT