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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define n  3 NEW_LINE int dp [ n ] [ n ] [ 2 ] ; bool v [ n ] [ n ] [ 2 ] ; int max ( int a , int b , int c ) { int m = a ; if ( m < b ) m = b ; if ( m < c ) m = c ; return m ; } int maxScore ( int arr [ ] [ n ] , int i , int j , int s ) { if ( i > n - 1 i < 0 j > n - 1 ) return 0 ; if ( i == 0 and j == n - 1 ) return arr [ i ] [ j ] ; if ( v [ i ] [ j ] [ s ] ) return dp [ i ] [ j ] [ s ] ; v [ i ] [ j ] [ s ] = 1 ; if ( ! s ) dp [ i ] [ j ] [ s ] = arr [ i ] [ j ] + max ( maxScore ( arr , i + 1 , j , s ) , maxScore ( arr , i , j + 1 , s ) , maxScore ( arr , i - 1 , j , ! s ) ) ; else dp [ i ] [ j ] [ s ] = arr [ i ] [ j ] + max ( maxScore ( arr , i - 1 , j , s ) , maxScore ( arr , i , j + 1 , s ) ) ; return dp [ i ] [ j ] [ s ] ; } int main ( ) { int arr [ n ] [ n ] = { { 1 , 1 , 1 } , { 1 , 5 , 1 } , { 1 , 1 , 1 } } ; cout << maxScore ( arr , 0 , 0 , 0 ) ; return 0 ; }