Minimum Cost Painting Houses

You are given N houses, where each house can be painted in one of three colors (red, green, or blue). The cost of painting each house with a certain color is provided. You must paint all houses such that no two adjacent houses have the same color, and the total cost is minimized.

Let \(cost[i][j]\) be the cost of painting the \(i^{th}\) house with color \(j\) (where \(j=0,1,2\) corresponding to red, green, blue respectively). The relationship can be formulated as:

\[ dp[i][j] = cost[i][j] + \min_{k \neq j} dp[i-1][k] \]

The answer is \(\min(dp[N-1][0], dp[N-1][1], dp[N-1][2])\).

inputFormat

The first line contains an integer N, the number of houses. Each of the following N lines contains three space-separated integers, representing the cost of painting the corresponding house in red, green, and blue respectively.

outputFormat

Output a single integer representing the minimum cost to paint all houses so that no two adjacent houses have the same color.

3
17 2 17
16 16 5
14 3 19

10