# [leetcode] Paint House I && II

here 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` is the cost of painting house 0 with color red;`costs` 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.

```// dp0[i] stores the minimum cost for painting i houses that the ith house should be printed with red
// dp1[i] stores the minimum cost for painting i houses that the ith house should be printed with blue
// dp2[i] stores the minimum cost for painting i houses that the ith house should be printed with green
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
int len = costs.size();
if(len == 0) return 0;
int dp0[len], dp1[len], dp2[len];
dp0 = costs;
dp1 = costs;
dp2 = costs;
for(int i = 1; i < costs.size(); i++){
dp0[i] = min(dp1[i - 1], dp2[i - 1]) + costs[i];
dp1[i] = min(dp0[i - 1], dp2[i - 1]) + costs[i];
dp2[i] = min(dp1[i - 1], dp0[i - 1]) + costs[i];
}
return min(dp0[len - 1], min(dp1[len - 1], dp2[len - 1]));
}
};```

Paint House II

here 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?

O(nk^2) Solution

```class Solution {
public:
int MAX_INT = 0x7fffffff;
int minCostII(vector<vector<int>>& costs) {
int n = costs.size();
if(n == 0) return 0;
int k = costs.size();
if(k == 0) return 0;
int dp[n][k];
for(int i = 0; i < k; i++){
dp[i] = costs[i];
}
for(int i = 1; i < n; i++){
for(int j = 0; j < k; j++){
int minCost = MAX_INT;
for(int l = 0; l < k; l++){
if(l == j) continue;
minCost = dp[i - 1][l] < minCost? dp[i - 1][l]: minCost;
}
dp[i][j] = minCost + costs[i][j];
}
}
int ans = MAX_INT;
for(int i = 0; i < k; i++){
ans = dp[n - 1][i] < ans? dp[n - 1][i]: ans;
}
return ans;
}
};```

O(nk) solution

The original bottleneck is the calculation of minCost of dp[i – 1][l], which hinders the performance.

This new solution stores 2 minimum costs in dp[i – 1][1~k]. There is no need to calculate it again and again which is a waste of time.

```class Solution {
public:
int MAX_INT = 0x7fffffff;
int minCostII(vector<vector<int>>& costs) {
int n = costs.size();
if(n == 0) return 0;
int k = costs.size();
if(k == 0) return 0;
int dp[n][k];
for(int i = 0; i < k; i++){
dp[i] = costs[i];
}
for(int i = 1; i < n; i++){
int minCosts;
minCosts = MAX_INT;
minCosts = MAX_INT;
for(int j = 0; j < k; j++){
if(dp[i - 1][j] <= minCosts){
minCosts = minCosts;
minCosts = dp[i - 1][j];
}
else if(dp[i - 1][j] <= minCosts){
minCosts = dp[i - 1][j];
}
}
for(int j = 0; j < k; j++){
int minCost = minCosts;
if(dp[i - 1][j] == minCost){
minCost = minCosts;
}
dp[i][j] = minCost + costs[i][j];
}
}
int ans = MAX_INT;
for(int i = 0; i < k; i++){
ans = dp[n - 1][i] < ans? dp[n - 1][i]: ans;
}
return ans;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.