Maximise matrix sum by following the given Path | C # 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
using System ; class GFG { static int n = 3 ; static int [ , , ] dp = new int [ n , n , 2 ] ; static bool [ , , ] v = new bool [ 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 ] ; } static public void Main ( ) { int [ , ] arr = { { 1 , 1 , 1 } , { 1 , 5 , 1 } , { 1 , 1 , 1 } } ; Console . WriteLine ( maxScore ( arr , 0 , 0 , 0 ) ) ; } }