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[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.

 
Note:
All costs are positive integers.
 
Follow up:
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[0][j] = cost[0][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: