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, 6 weeks ago, In English,

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[0][0] is the cost of painting house 0 with color 0; costs[1][2] 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[0].size();
        
        int dp[n][k];
        int min1=INT_MAX;
        int min2=INT_MAX;
        int minind=-1;
        for(int i=0;i<k;i++){
            dp[0][i]=cost[0][i];
            if(cost[0][i]<min1){
                min2=min1;
                minind=i;
                min1=cost[0][i];
            }else min2=min(min2,cost[0][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;
    }
};
 
 
 
 
  • Vote: I like it
  • -6
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by acash (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Is this problem available on a different OJ? You need to have subscription on LeetCode for this problem.