PaintHouseII.java

public class PaintHouseII {

    /**
     * 思路很简单，只要记录上一个house为止的最小cost及index以及次小cost即可
     * 遍历当前house的各种颜色，如果当前颜色和上个house最小cost的颜色不同，则上个house可以取最小cost，否则取次小cost
     */
    public int minCostII(int[][] costs) {
        if (costs.length == 0) {
            return 0;
        }
        int k = costs[0].length;
        int min = 0, minIdx = -1, submin = 0;
        for (int i = 0; i < costs.length; i++) {
            int min0 = Integer.MAX_VALUE, minIdx0 = -1, submin0 = Integer.MAX_VALUE;
            for (int j = 0; j < k; j++) {
                int cost = costs[i][j] + (j != minIdx ? min : submin);
                if (cost < min0) {
                    submin0 = min0;
                    min0 = cost;
                    minIdx0 = j;
                } else if (cost < submin0) {
                    submin0 = cost;
                }
            }
            min = min0; minIdx = minIdx0; submin = submin0;
        }
        return min;
    }
}