Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### acash's blog

By acash, history, 5 weeks ago, , https://leetcode.com/problems/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 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.

I am unable to pass all the test cases

class Solution {
public:
int minCostII(vector<vector<int>>& cost) {
if(cost.size()==0)return 0;
int n=cost.size();
int k=cost.size();

int dp[n][k];
int min1=INT_MAX;
int min2=INT_MAX;
int minind=-1;
for(int i=0;i<k;i++){
dp[i]=cost[i];
if(cost[i]<min1){
min2=min1;
minind=i;
min1=cost[i];
}else min2=min(min2,cost[i]);

}
cout<<min2;
for(int i=1;i<n;i++){
int curmin=INT_MAX;
int curmin2=INT_MAX;
int curind=0;
for(int j=0;j<k;j++){
if(minind!=j){
dp[i][j]=min1+cost[i][j];
}else{
dp[i][j]=min2+cost[i][j];
}
if(curmin>dp[i][j]){
curmin2=curmin;
curmin=dp[i][j];
minind=j;

}else curmin2=min(curmin2,dp[i][j]);

}
min1=curmin;
min2=curmin2;
minind=curind;
}

return min1;
}
}; Comments (3)
 » Auto comment: topic has been updated by acash (previous revision, new revision, compare).
 » HINT: Think of dp[i][j] state as the minimal cost of painting first i houses so the last one is painted in color j.
 » Is this problem available on a different OJ? You need to have subscription on LeetCode for this problem.