265. Paint House II

dp[h][c] -> the min cost to paint house h with color c
Naive的思路是在iterate 当前house的k 个color的同时， 再 iterate 前一个house的k个color, 在前一个不等于当前色的cost中找min
但是这里要求O(nk) instead of O(nkk), 所以观察了一下发现对于prev只需要一个min1 和一个min2
具体代码还可以简化，譬如引入prevMin1 和prevMin2 -> 可以避免做两次for (int c = 0; c < COLOR; c++)

还看到有Override costs array的做到Space O(1), 但是我感觉改变input并不好

一刷
69.77 %
class Solution {
    public int minCostII(int[][] costs) {
        // dp[h][c] -> the min cost to paint house h with color c
        if (costs == null || costs.length == 0 || costs[0] == null || costs[0].length == 0) {
            return 0;
        }
        int HOUSE = costs.length;
        int COLOR = costs[0].length;
        int[][] dp = new int[HOUSE][COLOR];
        int min1 = -1;
        int min2 = -1;
        for (int i = 0; i < COLOR; i++) {
            //  min1   min2
            if (min1 == -1 || costs[0][i] <= costs[0][min1]) {
                min2 = min1;
                min1 = i;
            } else if (min2 == -1 || costs[0][i] < costs[0][min2]) {
                min2 = i;
            }
            dp[0][i] = costs[0][i];
            // System.out.println("min1 -> " + min1 + "min2 -> " + min2);
        }
        for (int h = 1; h < HOUSE; h++) {
            for (int c = 0; c < COLOR; c++) {
                if (c == min1) {
                    dp[h][c] = dp[h - 1][min2] + costs[h][c];
                } else {
                    dp[h][c] = dp[h - 1][min1] + costs[h][c];
                }
                // System.out.println(dp[h][c]);
            }
            min1 = -1;
            min2 = -1;
            for (int c = 0; c < COLOR; c++) {
                if (min1 == -1 || dp[h][c] <= dp[h][min1]) {
                    min2 = min1;
                    min1 = c;
                } else if (min2 == -1 || dp[h][c] < dp[h][min2]) {
                    min2 = c;
                }
            }
        }
        return dp[costs.length - 1][min1];
    }
}