# 28ms C++ Solution with Comments Using DP

• ``````class Solution {
public: int minCostII(vector<vector<int>>& costs) {
// corner case
if(costs.size() ==0){
return 0;
}
if(costs[0].size() ==0){
return 0;
}
// create a matrix for dynamic programming
// dp[i][j] will be the minimum total cost up to (i+1) th house if (i+1)th house
// is painted with color j+1.
// (0th row represent the cost for the first house)
vector<vector<int> > dp(costs.size(),vector<int>(costs[0].size(),0));

// create variables for find the smallest cost for the first house as
// well as the second smallest cost for the first house

int min = numeric_limits<int>::max();
int secmin = numeric_limits<int>::max();
int min_index = -1;
int secmin_index = -1;
for(int j = 0; j<costs[0].size();j++){
if(costs[0][j]<min)
{
secmin = min;
secmin_index = min_index;
min = costs[0][j];
min_index = j;

}
else if(costs[0][j]<secmin)
{
secmin = costs[0][j];
secmin_index = j;
}
dp[0][j] = costs[0][j];

}

int prev_row_min_index = min_index;
int prev_row_secmin_index = secmin_index;

// the update formula is
// dp[i][j] = cost[i][j]+ min(dp[i-1][j']) where j' is not j.
// min(dp[i-1][j']) is the smallest one on i-1 th row if dp[i-1][j] is not the smallest one in i-1th row.
// min(dp[i-1)[j']) is the second smallest one if dp[i-1][j] is  the smallest one in i-1th row.

for(int i = 1; i<costs.size(); i++){
int min = numeric_limits<int>::max();
int secmin = numeric_limits<int>::max();

for(int j = 0; j<costs[0].size();j++){

if(j == prev_row_min_index){
dp[i][j] = costs[i][j]+ dp[i-1][prev_row_secmin_index];
}else{
dp[i][j] = costs[i][j]+ dp[i-1][prev_row_min_index];
}

if(dp[i][j]<min){
secmin = min;
secmin_index = min_index;
min = dp[i][j];
min_index = j;
}
else if(dp[i][j]<secmin){
secmin = dp[i][j];
secmin_index = j;

}

}
prev_row_min_index = min_index;
prev_row_secmin_index = secmin_index;

}

return dp[costs.size()-1][min_index];
} };``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.