- You are given a number n, representing the number of houses.
- In the next n rows, you are given 3 space separated numbers representing the cost of painting nth house with red or blue or green color.
- You are required to calculate and print the minimum cost of painting all houses without painting any consecutive house with the same color.
This question uses the same trick as the previous question, "Maximum Sum Non-adjacent Elements". Refer to that question if you haven't already.
Let's understand this problem through the example given in the problem statement.
In figure 1,the x-axis denotes the number of houses and the y-axis denotes the colors they are to be painted with. These colors are red, blue and green.
For example, the first cell of the first row and column denotes that the cost of painting House no. '1' with red color is 1.
So, we are required to paint a house with a color such that no adjacent houses are painted with the same color.
Hence, just like in the question "Maximum Sum Non-Adjacent Elements", if a color is included in the previous house then it has to be excluded from the current house.
Let's discuss the solution part now.