256. Paint House

There are a row of n houses, 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.

Solution: Create a nx3 DP array. For each house, calculating the cost of painting it to each of 3 colors. the accumulated cost for each color at position i is the cost of paiting ith house to that color plus the minimum of accumulated cost until position j - 1 of the other two colors.

    public int minCost(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }
        int n = costs.length;
        int[][] dp = new int[n + 1][3];
        for (int i = 0; i < n; i++) {
            dp[i + 1][0] = costs[i][0] + Math.min(dp[i][1], dp[i][2]);
            dp[i + 1][1] = costs[i][1] + Math.min(dp[i][0], dp[i][2]);
            dp[i + 1][2] = costs[i][2] + Math.min(dp[i][0], dp[i][1]);
        }
        return Math.min(Math.min(dp[n][0], dp[n][1]), dp[n][2]);
    }

265. 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 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.

Follow up:
Could you solve it inO(nk) runtime?

Solution: We can simply follow the way in I. But that will need iterating all k numbers for each new color, which will be give a n*k^2 time complexity. Even with a priorityQueue, it will be n*K*logK. We can find that only two minimum numbers from previous step is needed. If the min number is from the same color we select another. Otherwise use the smaller one.

    public int minCostII(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }

        int len = costs.length;
        int k = costs[0].length;

        //two min costs from the last house, maitaning mins[0] <= mins[1]
        int[] mins = new int[2];
        int[] dp = new int[k];
        for (int i = 0; i < len; i++) {
            int[] mins2 = new int[2];
            for (int j = 0; j < k; j++) {
                dp[j] = costs[i][j] + (dp[j] == mins[0] ? mins[1] : mins[0]);
                if (mins2[0] == 0) {
                    mins2[0] = dp[j];
                } else if (mins2[1] == 0 || mins2[1] > dp[j]) {
                    mins2[1] = dp[j];
                }
                if (mins2[1] < mins2[0]) {
                    int tmp = mins2[1];
                    mins2[1] = mins2[0];
                    mins2[0] = tmp;
                }
            }
            mins[0] = mins2[0];
            mins[1] = mins2[1];
        }

        return mins[0] == 0 ? mins[1] : mins[0];
    }