acash's blog

By acash, history, 5 years ago, In English

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.

  • Vote: I like it
  • -12
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

where is the problem? I think you are better to show the links of the problem when you ask.Sorry for my poor English.