Treasure and Cities | A memoization based program to find maximum treasure that can be collected . ; k is current index and col is previous color . ; base case ; we have two options either visit current city or skip that ; check if color of this city is equal to prev visited city ; return max of both options ; Driver code
MAX = 1001 NEW_LINE dp = [ [ - 1 for i in range ( MAX ) ] for i in range ( MAX ) ] NEW_LINE def MaxProfit ( treasure , color , n , k , col , A , B ) : NEW_LINE INDENT if ( k == n ) : NEW_LINE INDENT dp [ k ] [ col ] = 0 NEW_LINE return dp [ k ] [ col ] NEW_LINE DEDENT if ( dp [ k ] [ col ] != - 1 ) : NEW_LINE INDENT return dp [ k ] [ col ] NEW_LINE DEDENT summ = 0 NEW_LINE if ( col == color [ k ] ) : NEW_LINE INDENT summ += max ( A * treasure [ k ] + MaxProfit ( treasure , color , n , k + 1 , color [ k ] , A , B ) , MaxProfit ( treasure , color , n , k + 1 , col , A , B ) ) NEW_LINE DEDENT else : NEW_LINE INDENT summ += max ( B * treasure [ k ] + MaxProfit ( treasure , color , n , k + 1 , color [ k ] , A , B ) , MaxProfit ( treasure , color , n , k + 1 , col , A , B ) ) NEW_LINE DEDENT dp [ k ] [ col ] = summ NEW_LINE return dp [ k ] [ col ] NEW_LINE DEDENT A = - 5 NEW_LINE B = 7 NEW_LINE treasure = [ 4 , 8 , 2 , 9 ] NEW_LINE color = [ 2 , 2 , 6 , 2 ] NEW_LINE n = len ( color ) NEW_LINE print ( MaxProfit ( treasure , color , n , 0 , 0 , A , B ) ) NEW_LINE