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 English acash 2019-10-05 14:12:20 2 Tiny change: 'ne of the k colors. T' -> 'ne of the m colors. T' (published)
en2 English 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 English acash 2019-10-05 14:11:12 1599 Initial revision (published)