Problem:

There are a row of *n* houses, each house can be painted with one of the *k* colors. 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

cost matrix. For example,*n* x *k*`costs[0][0]`

is the cost of painting house 0 with color 0; `costs[1][2]`

is the cost of painting house 1 with color 2, and so on… Find the minimum cost to paint all houses.

**Solution**. This problem is pretty similar to Lowest cost to adjust integer array, adjacencies differ less than k. dp[i][j] is calculated by each value in dp[i – 1] level.

We define dp[][]. Considering we already painted house [0,…,i], dp[i][j] means the minimum price when house i paints with color j.

Let minPos[i] is the color of the lowest price when we paint till house i

min1[i] is the lowest price when we paint till house i.

min2[i] is the second lowest price when we paint till house.

Then we have dp[i][j] = cost[i][j] + {

min1, when j != minPos[i – 1]

min2, when j == minPos[i – 1] }

dp[1][0] = cost[1][0] + min2[0] = 3 + 2

dp[1][1] = cost[1][1] + min1[0] = 2 + 1

No code for this problem because I don’t have premium access to leetcode or test cases.