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 for ( int i = 0 ; i < n ; i ++ ) Arrays . fill ( dp [ i ] , - 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 ]
#include <bits/stdc++.h> NEW_LINE #define COL  5 NEW_LINE #define ROW  5 NEW_LINE using namespace std ; int totalPaths ( int i , int j , int n , int grid [ ] [ COL ] , int dp [ ] [ COL ] ) { 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 ] ; } int maxSumPath ( int i , int j , int n , int grid [ ROW ] [ COL ] , int dp [ ROW ] [ COL ] ) { 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 ] + max ( maxSumPath ( i , j + 1 , n , grid , dp ) , maxSumPath ( i + 1 , j , n , grid , dp ) ) ; } return dp [ i ] [ j ] ; } int main ( ) { int grid [ ROW ] [ COL ] = { { 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 = ROW ; int dp [ ROW ] [ COL ] ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) dp [ i ] [ j ] = -1 ; } dp [ n - 1 ] [ n - 1 ] = 1 ; cout << " Total ▁ paths : ▁ " << totalPaths ( 0 , 0 , n , grid , dp ) << endl ; 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 ] ; cout << " Maximum ▁ sum : ▁ " << maxSumPath ( 0 , 0 , n , grid , dp ) << endl ; return 0 ; }