acash's blog

By acash, history, 2 months ago, ,

There are a row of n houses, each house can be painted with one of the m 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, and you need to cost the least. Return the minimum cost. Generally this problem is asked for 3 colors but I am doing it for m colors. I have commented my solution.

    int minCost(vector<vector<int>> &costs) {

if(costs.size()==0)return 0;
int n = costs.size();
int m = costs[0].size();
int dp[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
dp[i][j] = INT_MAX;
}
}
for(int i=0;i<n;i++){
dp[0][i]=costs[0][i];
}
//dp[i][j] represents min cost to paint ith house with jth colour
for(int i=1;i<n;i++){
for(int j=0;j<m;j++){
//searching min cost in previous row
for(int k=0;k<m;k++){
if(j!=k){  //no two adjacent house can have same color
dp[i][j]=min(dp[i][j],dp[i-1][k]);
}
}
dp[i][j]+=costs[i][j];
}
}
int ans=INT_MAX;
//picking minimum from last row
for(int i=0;i<m;i++){
ans=min(ans,dp[n-1][i]);
}
return ans;

}


I am failing on some of test cases.Test cases seems to be large,I am unable to find where i am doing wrong.

• -12

 » 2 months ago, # |   0 Auto comment: topic has been updated by acash (previous revision, new revision, compare).
 » 2 months ago, # |   0 where is the problem? I think you are better to show the links of the problem when you ask.Sorry for my poor English.