Sudo Placement [ 1.5 ] | Wolfish | Python program for SP - Wolfish ; Function to find the maxCost of path from ( n - 1 , n - 1 ) to ( 0 , 0 ) ; base condition ; reaches the point ; if the state has been visited previously ; i + j ; check if it is a power of 2 , then only move diagonally ; if not a power of 2 then move side - wise ; Function to return the maximum cost ; calling dp function to get the answer ; Driver Code ; Function calling to get the answer
size = 1000 ; NEW_LINE def maxCost ( a , m , n , dp ) : NEW_LINE INDENT if ( n < 0 or m < 0 ) : NEW_LINE INDENT return int ( - 1e9 ) ; NEW_LINE DEDENT elif ( m == 0 and n == 0 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT elif ( dp [ m ] [ n ] != - 1 ) : NEW_LINE INDENT return dp [ m ] [ n ] ; NEW_LINE DEDENT else : NEW_LINE INDENT num = m + n ; NEW_LINE if ( ( num & ( num - 1 ) ) == 0 ) : NEW_LINE INDENT dp [ m ] [ n ] = a [ m ] [ n ] + maxCost ( a , m - 1 , n - 1 , dp ) ; NEW_LINE return dp [ m ] [ n ] ; NEW_LINE DEDENT else : NEW_LINE INDENT dp [ m ] [ n ] = ( a [ m ] [ n ] + max ( maxCost ( a , m - 1 , n , dp ) , maxCost ( a , m , n - 1 , dp ) ) ) ; NEW_LINE return dp [ m ] [ n ] ; NEW_LINE DEDENT DEDENT DEDENT def answer ( a , n ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( size ) ] for j in range ( size ) ] ; NEW_LINE for i in range ( size ) : NEW_LINE INDENT for j in range ( size ) : NEW_LINE INDENT dp [ i ] [ j ] = - 1 ; NEW_LINE DEDENT DEDENT return maxCost ( a , n - 1 , n - 1 , dp ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = [ [ 1 , 2 , 3 , 1 ] , [ 4 , 5 , 6 , 1 ] , [ 7 , 8 , 9 , 1 ] , [ 1 , 1 , 1 , 1 ] ] ; NEW_LINE n = 4 ; NEW_LINE print ( answer ( a , n ) ) ; NEW_LINE DEDENT