So taking an example, where n = 4 (number of houses) and k = 6 (color options: c1, c2, c3, c4, c5, c6). And corresponding cost of color of painting the House (h1, h2, h3 and h4) with colors (c1, c2, c3, c4 ,c5, c6) respectively is shown in figure. Our aim is to minimize the total cost of painting all 4 houses such that no 2 consecutive houses have the same color.
- Now we will prepare a dp matrix for storing the minimal total cost at each level while considering choosing each color without violating the condition.
- But before moving further, make sure that you first fill, row of dp with corresponding value of cost of color to paint house 1 because the total minimal cost to paint house 1 when choosing one color option at a time will simply be the cost of painting house 1 with corresponding color.
- That means if we are to paint house 2 with color 4 then we will look for minimal cost of painting house 1 except the cost of color 4 itself (so that the condition of 2 consecutive houses with the same color does get violated) and add cost of color 4 in painting house 2.
- So the minimal cost of painting house 1 excluding the option for color 4 itself is 1 and adding the cost of painting house 2 with color 4 i.e. 3 we get 4, so we will store 4 in dp matrix at (h2, c2).
- In a similar pattern we fill each and every index of dp. In the above diagram, we have filled the dp till house 3. Try to fill dp for house 4 (i.e. fourth row )
Let's try to code this.
First of all we take input for n (number of houses), k (number of colors) and in the next n rows, for k space separated numbers representing the cost of painting nth house with one of the k colors.
Then we define a n*k 2d array and fill its first row with cost of painting house 1 for different color.
Then we apply a nested for loop for traversing dp for filling it. Inside it we initially define it for maximum value. Then we find the minimum value of the previous row excluding the value of the corresponding color at which we are now in order to avoid 2 houses of similar color. After finding the minimum value, we add this to the current value of color j of house i and store it in corresponding dp.
After filling all the rows successfully using the above code, we need to find the minimum of the last row in order to have our final answer.