# Leetcode – Paint House II solution (Java)

Tags: , ,

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 `n x k` cost matrix.

For example, `costs` is the cost of painting house 0 with color 0; `costs` is the cost of painting house 1 with color 2, and so on… Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Could you solve it in O(nk) runtime?

#### Analysis

This is a follow up question of Paint House I. The basic idea to solve Paint House I is to define `DP[i][j]` as the minimum cost to paint house `until i` with color `j`. where` i  ∈ [1, n]  and j ∈ {0, 1, 2}.`

In the beginning, DP[j] = cost[j].  Then we can use the following rules to update the table in bottom up manner.

For this problem, we can also define `DP[i][j]` as the minimum cost to paint house `until i` with `color j`

Then `DP[i][j]` = `cost[i][j]` + min({`DP[i - 1][m]` | m = 0, 1, 2, …., k and m != j }). We can use an variable `preMin` to record the minimum cost of DP[i – 1] [m], and the corresponding color `minColor`

One problem is that the `minColor` (color `k` with minimum value) can equal to the current color.  In this case we need to use the color with second smallest cost. So define another variable secondMin to record the second minimum cost of DP[i – 1][m] along with the corresponding color `secondMinColor`

The following is the implementation in Java: