## Paint House

Question 1

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.

Solution

DP.

O(1) space from here.

``````//C++: 12ms
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
int n = costs.size();
if(n==0) return 0;
for(int i=1; i<n; ++i){
for(int j=0; j<3; ++j){
costs[i][j] += min(costs[i-1][(j+1)%3], costs[i-1][(j+2)%3]);
}
}
return min(costs[n-1][0], min(costs[n-1][1], costs[n-1][2]));
}
};
``````

or here.

``````class Solution {
public:
int minCost(vector<vector<int>>& costs) {
if (costs.empty()) return 0;
int n = costs.size(), r = 0, g = 0, b = 0;
for (int i = 0; i < n; i++) {
int rr = r, bb = b, gg = g;
r = costs[i][0] + min(bb, gg);
b = costs[i][1] + min(rr, gg);
g = costs[i][2] + min(rr, bb);
}
return min(r, min(b, g));
}
};
``````

another O(n) space from here

``````public int minPaintCost(int[][] cost) {
if (cost == null || cost.length == 0) return 0;
int[][] dp = new int[cost.length][3];
dp[0][0] = cost[0][0], dp[0][1] = cost[0][1], dp[0][2] = cost[0][2];
for (int i = 1; i < cost.length; ++i) {
dp[i][0] = cost[i][0] + Math.min(dp[i-1][1], dp[i-1][2]);
dp[i][1] = cost[i][1] + Math.min(dp[i-1][0], dp[i-1][2]);
dp[i][2] = cost[i][2] + Math.min(dp[i-1][0], dp[i-1][1]);
}
return Math.min(dp[dp.length-1][0], Math.min(dp[dp.length-1][1],[dp.length-1][2]));
}
``````

Question 2

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?

Solution

dp: maintain the minimum two costs min1(smallest) and min2 (second to smallest) after painting i-th house.

from here

``````class Solution {
public:
int minCostII(vector<vector<int>>& costs) {
if (costs.empty()) return 0;
int n = costs.size(), k = costs[0].size(), min1, min2;
vector<int> dp(k, 0);
for (int i = 0; i < n; i++) {
int premin1 = i ? min1 : 0, premin2 = i ? min2 : 0;
min1 = min2 = INT_MAX;
for (int j = 0; j < k; j++) {
if (dp[j] != premin1 || premin1 == premin2)
dp[j] = premin1 + costs[i][j];
// pre_min1 occurred when painting house i-1 with color j,
// so it cannot be added to dp[j]
else dp[j] = premin2 + costs[i][j];
if (min1 <= dp[j]) min2 = min(min2, dp[j]);
else min2 = min1, min1 = dp[j];
}
}
return min1;
}
};
``````