Maximise matrix sum by following the given Path | Javascript 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
let n = 3 ; let dp = new Array ( n ) ; let v = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) { dp [ i ] = new Array ( n ) ; v [ i ] = new Array ( n ) ; for ( let j = 0 ; j < n ; j ++ ) { dp [ i ] [ j ] = new Array ( 2 ) ; v [ i ] [ j ] = new Array ( 2 ) ; for ( let k = 0 ; k < 2 ; k ++ ) { dp [ i ] [ j ] [ k ] = 0 ; v [ i ] [ j ] [ k ] = 0 ; } } } function max ( a , b , c ) { let m = a ; if ( m < b ) { m = b ; } if ( m < c ) { m = c ; } return m ; } function maxScore ( arr , i , j , 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 ] ; } let arr = [ [ 1 , 1 , 1 ] , [ 1 , 5 , 1 ] , [ 1 , 1 , 1 ] ] ; document . write ( maxScore ( arr , 0 , 0 , 0 ) ) ;