Coloring Houses

There are N houses in a row. Each house can be painted in either Red, Green or Blue color. The cost of coloring each house in each of the colors is different.

Find the color of each house such that no two adjacent house have the same color and the total cost of coloring all the houses is minimum.

Hint:The question intends to state that cost of painting any house in any color is different, so if cost of painting House 1 in Red is say, X then the cost of painting House 2 in red will some other value Y. It can be considered each house has different dimensions and hence cost of painting in each color is different, and the cost of paint for each house also varies 

Strategy:

This problem can be modeled as a Dynamic Programming problem. The DP equation can be given as

C[i][c] = H[c] + min(C[i-1][x]) 
                          x ∈ {Red, Blue, Green}
                          x ≠ c

Here C[i][c] is the cost of painting the row of houses ending at the i^th house such that the i^th house is painted in color 'c' and c is chosen such that the previous house is not in the same color. 

Food for Thought: An easier variant of the same problem, that can be solved using Greedy Approach will be when the cost of painting any house in any color is the same. In this case how will you paint the houses?