265. Paint House II - cocoder39/coco39_LC GitHub Wiki

class Solution {
public:
    int minCostII(vector<vector<int>>& costs) {
        int sz = costs.size();
        if (sz == 0) {
            return 0;
        }
        int k = costs[0].size();
        
        //new cost[i][j] is min total cost of painting house 0 to i and painting house i with color j
        for (int i = 1; i < sz; i++) {
            int secondMin;
            int minIdx = minCost(costs[i - 1], secondMin);
            for (int j = 0; j < k; j++) {
                if (j == minIdx) {
                    costs[i][j] += secondMin;
                }
                else {
                    costs[i][j] += costs[i - 1][minIdx];
                }
            }
        }
        
        int res = INT_MAX;
        for (auto cost : costs[sz - 1]) {
            res = min(res, cost);
        }
        return res;
    }
private:
    //cost is the costs of painting a house
    //second is the second min cost among all costs
    //return val is the index of the min cost among all costs
    int minCost(vector<int>& costs, int& secondMin) { //O(k)
        int res = costs[0] < costs[1] ? 0 : 1;
        int firstMin = costs[res];
        secondMin = costs[1 - res];
        
        for (int j = 2; j < costs.size(); j++) {
            if (costs[j] <= firstMin) {
                secondMin = firstMin;
                firstMin = costs[j];
                res = j;
            }
            else if (costs[j] < secondMin) { // && cost[j] >= first
                secondMin = costs[j];
            }
        }
        return res;
    }
};