Paint Houses 2 dp problem

#1

Problem Link-https://www.lintcode.com/problem/paint-house-ii/description

My soln-https://ide.codingblocks.com/s/356402

Please help me in understanding where my solution or approach is not working

#2

Hey @mridulmohanbagri17

        for(int i=0;i<m;i++)
        {
            dp[0][i]=costs[0][i];
            if(costs[0][i]<minimum){
                minimum=costs[0][i];
                s_minimum=minimum;
                continue;
            }
            
            if(costs[0][i]<s_minimum){
                s_minimum=costs[0][i];
            }
            
        }

Here you have written [0][m] in your code so corrected that
But from here minimum ans sminimum will be same so please rectify that first.

Also explain your algo in brief

#3

class Solution { public: /** * @param costs: n x k cost matrix * @return: an integer, the minimum cost to paint all houses */ int minCostII(vector<vector> &costs) { int n=costs.size(); if(n==0) return 0; int m=costs[0].size(); int dp[n][m]; int minimum=INT_MAX,s_minimum=INT_MAX; for(int i=0;i<m;i++) { dp[0][i]=costs[0][i]; if(costs[0][i]<minimum){ s_minimum=minimum; minimum=costs[0][i]; continue; } if(costs[0][i]<s_minimum){ s_minimum=costs[0][i]; } } for(int i=1;i<n;i++){ for(int j=0;j<m;j++){ if(dp[i-1][j]==minimum) dp[i][j]=s_minimum+costs[i][j]; else dp[i][j]=minimum+costs[i][j]; } minimum=s_minimum=INT_MAX; for(int k=0;k<m;k++){ if(dp[i][k]<minimum){ s_minimum=minimum; minimum=dp[i][k]; continue; } if(dp[i][k]<s_minimum){ s_minimum=dp[i][k]; } } } int answer=INT_MAX; for(int i=0;i<m;i++){ answer=min(answer,dp[n-1][i]); } return answer; } };

#4

Hey @mridulmohanbagri17
Share your code in Ide
and also explain your algo

#5
#6

…

#7

It worked sir ,thankyou I did a few silly mistakes.

1 Like
#8

What I did that for each house means for each row calculated the minimum and second minimum value and used that to calculate the value for the next row .It reduced the time complexity O(n3) to O(n2).

#9

Its resolved now ,right ?
Or do u still have any doubt in this ?

#10

No no it is resolved.