0

It's my first time trying to create recurrence relation . I am trying to build and expalin recurrence relation for the 3 colors house painting problem :

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red;costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

The algoritem to solve this problem is here :

http://happycoding2010.blogspot.co.il/2015/11/leetcode-256-paint-house.html

Any idea ?

benz
  • 101
  • Welcome to MSE! When posting a question one generally shows the advances one has made so far or the precise detail that makes this question hard to work out or hard to understand. It will be useful if you add them. –  May 23 '17 at 16:28
  • Unfortunately it's my first time and I don't know how to start I made this equation

    Cost[1][j%3] = min(Cost[i-1][(j+1)%3], Cost[i-1][(j+2)%3]) + Cost[i][j]

    using the internet and exmaples from class but I am not sure it's enough and if it get all the possibilities

     – benz May 23 '17 at 17:06
  • Hint: on entry into each iteration i the red, blue and green variables keep the minimum cost of painting all i preceding houses in such a way, that the last of them (i.e., the house at index i) is red, blue or green, respectively. In each iteration we find the cheapest combination of the current house color with non-colliding preceding solution. At the end of each iteration we have three smallest possible costs for a row of i+1 houses. Finally we choose the smallest of the three. – CiaPan Jun 21 '18 at 15:14
  • BTW, the code presented at happycoding blog is unnecessarily complicated: the internal if() is not necessary, the code in the else branch would correctly handle the i==0 case. – CiaPan Jun 21 '18 at 20:37

1 Answers1

0

As the code shows, the minimum possible total cost $T_i$ of painting $i$ houses can be calculated as a minimum of possible total costs $T_{i,r}$, $T_{i,b}$ and $T_{i,g}$ of painting $i$ houses so that the last of them is red, blue or green, respectively.

And we can paint the $i$-th house red if the $(i-1)$-st house is blue or green; or we can paint it blue, if the previous one is red or green; and finally we can paint it green if the previous one is red or blue.

So: $$T_i = \min\left\{ \begin{align} T_{i,r} &=\min( T_{i-1,b}, T_{i-1,g}) + C_{i,r} \\ T_{i,b} &=\min( T_{i-1,r}, T_{i-1,g}) + C_{i,b} \\ T_{i,g} &=\min( T_{i-1,r}, T_{i-1,b}) + C_{i,g} \end{align}\right.$$ where $C_{i,r}$, $C_{i,b}$ and $C_{i,g}$ – costs of painting the $i$-th house in respective colors.

The base case is: the cost of painting no house in any color is zero.

CiaPan
  • 13,049