Paint House DP (K-colors)

Revision en3, by acash, 2019-10-05 14:12:20

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.

#### History

Revisions

Rev. Lang. By When Δ Comment
en3 acash 2019-10-05 14:12:20 2 Tiny change: 'ne of the k colors. T' -> 'ne of the m colors. T' (published)
en2 acash 2019-10-05 14:11:38 2 Tiny change: 'ng it for k colors.\n' -> 'ng it for m colors.\n' (saved to drafts)
en1 acash 2019-10-05 14:11:12 1599 Initial revision (published)