256. Paint House

There are a row ofnhouses, each house can be painted with one of the three colors: red, blue or green. 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 anx3cost matrix. For example,costs[0][0]is the cost of painting house 0 with color red;costs[1][2]is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

S: DP

costSum[i][j]表示paint 0-i个房子，第i个房子刷j色时所需最小总花费，i只与i-1有关，可用一维数组

    int minCost(vector<vector<int>>& costs) {
        if (costs.size() == 0) return 0;
        vector<int> costSum = costs[0];
        for (int i = 1; i < costs.size(); ++i) {
            int preCost0 = costSum[0];
            int preCost1 = costSum[1];
            int preCost2 = costSum[2];
            costSum[0] = min(preCost1, preCost2) + costs[i][0];
            costSum[1] = min(preCost0, preCost2) + costs[i][1];
            costSum[2] = min(preCost1, preCost0) + costs[i][2];
        }
        return min(costSum[0], min(costSum[1], costSum[2]));
    }

265. Paint House II

There are a row ofnhouses, each house can be painted with one of thekcolors. 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 anxkcost 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.

Note:
All costs are positive integers.

S: DP O(nk)

preMin[i]表示涂到第i个房子所需的最小cost.每个房子取值情况只与其前一个房子有关，对第i个房子涂第j种色，

• 若取preMin[i-1]时前一个房子涂的不是第j色，只用将preMin[i-1]加上当前房子的cost即可;
• 否则取preMin2[i-1]，即涂到第i-1个房子第二小的cost加上当前cost

    int minCostII(vector<vector<int>>& costs) {
        int houseNum = costs.size();
        if (houseNum == 0) {
            return 0;
        }
        int colorNum = costs[0].size();
        int preMin1 = 0, preMin2 = 0, preColor1 = -1;
        for (int i = 0; i < houseNum; ++i) {
            int curMin1 = INT_MAX, curMin2 = INT_MAX, curColor1;
            for (int j = 0; j < colorNum; ++j) {
                int cur = j == preColor1? preMin2 : preMin1;
                cur += costs[i][j];
                if (cur < curMin1) {
                    curMin2 = curMin1;
                    curMin1 = cur;
                    curColor1 = j;
                } else if (cur < curMin2) {
                    curMin2 = cur;
                }
            }
            preMin1 = curMin1;
            preMin2 = curMin2;
            preColor1 = curColor1;
        }
        return preMin1;
    }