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 a n x k cost 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 in O(nk) runtime?

链接： http://leetcode.com/problems/paint-house-ii/

题解：

是Paint House I的generalized版本。这回颜色不是RGB三种，而是扩展到了K种。正好可以用上在Paint House I中没用上的东西。思路还是使用DP, 这回我们需要维护一个刷当前房子之前所有房子最小的花费min1，以及倒数第二小的花费min2。然后我们再遍历当前房子i所有color的花费，假如这个颜色与之前i-1号房子的颜色相同，我们选择min2，否则选择min1。比较完所有颜色以后我们记录下来当前的curMin1，curMin2以及current color， 更新min1，min2和lastColor，就可以继续计算下一个房子了。

Time Complexity - O(n)， Space Complexity - O(1)

public class Solution {
    public int minCostII(int[][] costs) {
        if(costs == null || costs.length == 0) {
            return 0;
        }
        int min1 = 0, min2 = 0, lastColor = -1;
        
        for(int i = 0; i < costs.length; i++) {
            int curMin1 = Integer.MAX_VALUE, curMin2 = Integer.MAX_VALUE, curColor = -1; 
            for(int j = 0; j < costs[0].length; j++) {          // loop through all colors
                int cost = costs[i][j] + (j == lastColor ? min2 : min1);
                if(cost < curMin1) {
                    curMin2 = curMin1;
                    curColor = j;
                    curMin1 = cost;
                } else if(cost < curMin2) {
                    curMin2 = cost;
                }
            }
            min1 = curMin1;
            min2 = curMin2;
            lastColor = curColor;
        }
        
        return min1;
    }
}

Reference:

https://leetcode.com/discuss/71995/easiest-o-1-space-java-solution

https://leetcode.com/discuss/52982/c-dp-time-o-nk-space-o-k

https://leetcode.com/discuss/54415/ac-java-solution-without-extra-space

https://leetcode.com/discuss/54290/accepted-simple-java-o-nk-solution

https://leetcode.com/discuss/60625/fast-dp-java-solution-runtime-o-nk-space-o-1

https://leetcode.com/discuss/68971/5-ms-java-solution-with-o-kn

http://www.cnblogs.com/jcliBlogger/p/4729957.html

https://leetcode.com/discuss/52937/1-line-python-solution-update-to-o-nk

265. Paint House II

原文：http://www.cnblogs.com/yrbbest/p/5020937.html