# Paint House I & II

Paint House I

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. 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 3` cost matrix. For example, `costs[0][0]` is the cost of painting house 0 with color red;`costs[1][2]` is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

```//dp[i][j]:minimum cost to paint first i houses with house i to be j color
//dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][j]
//given the color of house i
//find the min total cost to paint first i-1 houses
//0:red, 1:green, 2:blue
//time: O(nk) k: # of colors, n: # of houses
public int minCost(int[][] costs) {
if (costs == null || costs.length == 0 || costs[0].length == 0) {
return 0;
}
int row = costs.length;
int col = costs[0].length;
int[][] dp = new int[row][col];
//for house 0, dp[0][j] = costs[0][j]
for (int j = 0; j < col; j++) {
dp[0][j] = costs[0][j];
}
for (int i = 1; i < row; i++) {
for (int j = 0; j < col; j++) {
int min = Integer.MAX_VALUE;
//given the color of house i
//find the min total cost to paint first i-1 houses
for (int k = 0; k < col; k++) {
if (k == j) {
continue;
}
min = Math.min(min, dp[i - 1][k]);
}
dp[i][j] = min + costs[i][j];
}
}
int minCost = Integer.MAX_VALUE;
//return min in last row
for (int j = 0; j < col; j++) {
minCost = Math.min(minCost, dp[row - 1][j]);
}
return minCost;
}```

Paint House II

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.

Could you solve it in O(nk) runtime?

```public int minCostII(int[][] costs) {
if (costs == null || costs.length == 0 || costs[0].length == 0) {
return 0;
}
if (costs[0].length == 1) {
return costs[0][0];
}
int n = costs.length;
int k = costs[0].length;
//dp 2d array.
//minCost[i][j]: minimum cost to paint ith house with color j.
int[][] minCost = new int[n][k];
//minColor==i: for the current house, use ith color has smallest total value from house 0 ~ i
int minColor = -1;

//init first row(1st house)
int minValue = Integer.MAX_VALUE;
int secondMinValue = Integer.MAX_VALUE;
for (int j = 0; j < k; j++) {
minCost[0][j] = costs[0][j];
if (minCost[0][j] < minValue) {
//Important here!
//if there is a new min, then we need to compare the old min with the secondMinValue
secondMinValue = Math.min(secondMinValue, minValue);
minValue = minCost[0][j];
minColor = j;
} else if (minCost[0][j] < secondMinValue) {
secondMinValue = minCost[0][j];
}
}
int preMinValue, preSecondMinValue, preMinColor;
for (int i = 1; i < n; i++) {
preMinColor = minColor;
preMinValue = minValue;
preSecondMinValue = secondMinValue;
minColor = -1;
minValue = Integer.MAX_VALUE;
secondMinValue = Integer.MAX_VALUE;
for (int j = 0; j < k; j++) {
//if minCost[i-1][j] is not the smallest
if (j != preMinColor) {
minCost[i][j] = preMinValue + costs[i][j];
}
//if minCost[i-1][j] is the smallest
//then we can only use the second smallest one
else {
minCost[i][j] = preSecondMinValue + costs[i][j];
}
if (minCost[i][j] < minValue) {
//Important here!
//if there is a new min, then we need to compare the old min with the secondMinValue
secondMinValue = Math.min(secondMinValue, minValue);
minValue = minCost[i][j];
minColor = j;
} else if (minCost[i][j] < secondMinValue) {
secondMinValue = minCost[i][j];
}
}
}
return minValue;
}```
Share