Maximise matrix sum by following the given Path | Java implementation of the approach ; To store the states of the DP ; Function to return the maximum of the three integers ; Function to return the maximum score ; Base cases ; If the state has already been solved then return it ; Marking the state as solved ; Growing phase ; } Shrinking phase ; Returning the solved state ; Driver code
class GFG { static int n = 3 ; static int [ ] [ ] [ ] dp = new int [ n ] [ n ] [ 2 ] ; static boolean [ ] [ ] [ ] v = new boolean [ n ] [ n ] [ 2 ] ; static int max ( int a , int b , int c ) { int m = a ; if ( m < b ) { m = b ; } if ( m < c ) { m = c ; } return m ; } static int maxScore ( int arr [ ] [ ] , int i , int j , int s ) { if ( i > n - 1 i < 0 j > n - 1 ) { return 0 ; } if ( i == 0 && j == n - 1 ) { return arr [ i ] [ j ] ; } if ( v [ i ] [ j ] [ s ] ) { return dp [ i ] [ j ] [ s ] ; } v [ i ] [ j ] [ s ] = true ; if ( s != 1 ) { dp [ i ] [ j ] [ s ] = arr [ i ] [ j ] + Math . max ( maxScore ( arr , i + 1 , j , s ) , Math . max ( maxScore ( arr , i , j + 1 , s ) , maxScore ( arr , i - 1 , j , ( s == 1 ) ? 0 : 1 ) ) ) ; else { dp [ i ] [ j ] [ s ] = arr [ i ] [ j ] + Math . max ( maxScore ( arr , i - 1 , j , s ) , maxScore ( arr , i , j + 1 , s ) ) ; } return dp [ i ] [ j ] [ s ] ; } public static void main ( String args [ ] ) { int arr [ ] [ ] = { { 1 , 1 , 1 } , { 1 , 5 , 1 } , { 1 , 1 , 1 } } ; System . out . println ( maxScore ( arr , 0 , 0 , 0 ) ) ; } }