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 ) | recursive approach ; base condition ; reaches the point ; 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 : list , m : int , n : int ) -> int : 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 else : NEW_LINE INDENT num = m + n NEW_LINE if ( num & ( num - 1 ) ) == 0 : NEW_LINE INDENT return a [ m ] [ n ] + maxCost ( a , m - 1 , n - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT return a [ m ] [ n ] + max ( maxCost ( a , m - 1 , n ) , maxCost ( a , m , n - 1 ) ) NEW_LINE DEDENT DEDENT DEDENT def answer ( a : list , n : int ) -> int : NEW_LINE INDENT return maxCost ( a , n - 1 , n - 1 ) 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