Minimize cost of painting N houses such that adjacent houses have different colors | Function to find the minimum cost of coloring the houses such that no two adjacent houses has the same color ; Corner Case ; Auxiliary 2D dp array ; Base Case ; If current house is colored with red the take min cost of previous houses colored with ( blue and green ) ; If current house is colored with blue the take min cost of previous houses colored with ( red and green ) ; If current house is colored with green the take min cost of previous houses colored with ( red and blue ) ; Print the min cost of the last painted house ; Driver Code ; Function Call
def minCost ( costs , N ) : NEW_LINE INDENT if ( N == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT dp = [ [ 0 for i in range ( 3 ) ] for j in range ( 3 ) ] NEW_LINE dp [ 0 ] [ 0 ] = costs [ 0 ] [ 0 ] NEW_LINE dp [ 0 ] [ 1 ] = costs [ 0 ] [ 1 ] NEW_LINE dp [ 0 ] [ 2 ] = costs [ 0 ] [ 2 ] NEW_LINE for i in range ( 1 , N , 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = min ( dp [ i - 1 ] [ 1 ] , dp [ i - 1 ] [ 2 ] ) + costs [ i ] [ 0 ] NEW_LINE dp [ i ] [ 1 ] = min ( dp [ i - 1 ] [ 0 ] , dp [ i - 1 ] [ 2 ] ) + costs [ i ] [ 1 ] NEW_LINE dp [ i ] [ 2 ] = min ( dp [ i - 1 ] [ 0 ] , dp [ i - 1 ] [ 1 ] ) + costs [ i ] [ 2 ] NEW_LINE DEDENT print ( min ( dp [ N - 1 ] [ 0 ] , min ( dp [ N - 1 ] [ 1 ] , dp [ N - 1 ] [ 2 ] ) ) ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT costs = [ [ 14 , 2 , 11 ] , [ 11 , 14 , 5 ] , [ 14 , 3 , 10 ] ] NEW_LINE N = len ( costs ) NEW_LINE minCost ( costs , N ) NEW_LINE DEDENT