Maximise matrix sum by following the given Path | Python3 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
import numpy as np NEW_LINE n = 3 NEW_LINE dp = np . zeros ( ( n , n , 2 ) ) ; NEW_LINE v = np . zeros ( ( n , n , 2 ) ) ; NEW_LINE def max_three ( a , b , c ) : NEW_LINE INDENT m = a ; NEW_LINE if ( m < b ) : NEW_LINE INDENT m = b ; NEW_LINE DEDENT if ( m < c ) : NEW_LINE INDENT m = c ; NEW_LINE DEDENT return m ; NEW_LINE DEDENT def maxScore ( arr , i , j , s ) : NEW_LINE INDENT if ( i > n - 1 or i < 0 or j > n - 1 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( i == 0 and j == n - 1 ) : NEW_LINE INDENT return arr [ i ] [ j ] ; NEW_LINE DEDENT if ( v [ i ] [ j ] [ s ] ) : NEW_LINE INDENT return dp [ i ] [ j ] [ s ] ; NEW_LINE DEDENT v [ i ] [ j ] [ s ] = 1 ; NEW_LINE if ( not bool ( s ) ) : NEW_LINE INDENT dp [ i ] [ j ] [ s ] = arr [ i ] [ j ] + max_three ( maxScore ( arr , i + 1 , j , s ) , maxScore ( arr , i , j + 1 , s ) , maxScore ( arr , i - 1 , j , not bool ( s ) ) ) ; NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] [ s ] = arr [ i ] [ j ] + max ( maxScore ( arr , i - 1 , j , s ) , maxScore ( arr , i , j + 1 , s ) ) ; NEW_LINE DEDENT return dp [ i ] [ j ] [ s ] ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ [ 1 , 1 , 1 ] , [ 1 , 5 , 1 ] , [ 1 , 1 , 1 ] , ] ; NEW_LINE print ( maxScore ( arr , 0 , 0 , 0 ) ) ; NEW_LINE DEDENT