Paths from entry to exit in matrix and maximum path sum | C # implementation of the approach ; 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 [ , ] 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 [ , ] 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 ]
using System ; class GFG { static int totalPaths ( int i , int j , int n , int [ , ] grid , int [ , ] dp ) { if ( i < 0 j < 0 i >= n j >= n ) return 0 ; if ( dp [ i , j ] == - 1 ) { if ( grid [ i , j ] == 1 ) dp [ i , j ] = totalPaths ( i , j + 1 , n , grid , dp ) ; else if ( 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 ] ; } static int maxSumPath ( int i , int j , int n , int [ , ] grid , int [ , ] dp ) { if ( i < 0 j < 0 i >= n 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 ) ; else if ( grid [ i , j ] == 2 ) dp [ i , j ] = grid [ i , j ] + maxSumPath ( i + 1 , j , n , grid , dp ) ; else dp [ i , j ] = grid [ i , j ] + Math . Max ( maxSumPath ( i , j + 1 , n , grid , dp ) , maxSumPath ( i + 1 , j , n , grid , dp ) ) ; } return dp [ i , j ] ; } public static void Main ( String [ ] args ) { int [ , ] 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 } } ; int n = grid . GetLength ( 0 ) ; int [ , ] dp = new int [ n , n ] ; for ( int i = 0 ; i < n ; i ++ ) for ( int j = 0 ; j < n ; j ++ ) dp [ i , j ] = - 1 ; dp [ n - 1 , n - 1 ] = 1 ; Console . WriteLine ( " Total ▁ paths : ▁ " + totalPaths ( 0 , 0 , n , grid , dp ) ) ; for ( int i = 0 ; i < n ; i ++ ) for ( int j = 0 ; j < n ; j ++ ) dp [ i , j ] = - 1 ; dp [ n - 1 , n - 1 ] = grid [ n - 1 , n - 1 ] ; Console . WriteLine ( " Maximum ▁ sum : ▁ " + maxSumPath ( 0 , 0 , n , grid , dp ) ) ; } }