265. Paint House II

刷
July-25-2019

DP题做了几道我也发现共性了，就是每道我都不会。
这道题要这么想：
n位置的最优解是cost[n]里最小的+best[n-1]。问题出在，当前K中里最便宜的情况，有可能和n-1最优解时的颜色一样，在遍历cost[0~k]的时候，如果颜色和上次最优解一样，就要当前COST+n-1的次优解。
所以每次需要记录的：最优解，次优解，和这次的颜色。
题里说单独位置每种颜色价钱不一样。这里其实我没想明白，假如有一样的情况，有可能某位置出现3个最优解，下个位置就没法保证选的是正确的颜色，因为解可能在忽略的第三种里？因为我觉得如果有2个最优解，是无所谓的= =因为无非颜色是和上次的最优相同，或者不同，只要保证不同就行了。
不知道想的对不对。

    public int minCostII(int[][] costs) {
        if (costs.length == 0) return 0;
        
        int prevMin1 = 0;
        int prevMin2 = 0;
        int prevColor = -1;
        
        for (int i = 0; i < costs.length; i ++) {
            int tempMin1 = Integer.MAX_VALUE;
            int tempMin2 = Integer.MAX_VALUE;
            int tempColor = -1;
            for (int j = 0; j < costs[i].length; j ++) {
                
                int costWithPrev = costs[i][j];
                costWithPrev += j == prevColor ? prevMin2 : prevMin1;

                if (costWithPrev < tempMin1) {
                    tempMin2 = tempMin1;
                    tempMin1 = costWithPrev;
                    tempColor = j;
                } else if (costWithPrev < tempMin2) {
                    tempMin2 = costWithPrev;
                }
            }
            prevMin1 = tempMin1;
            prevMin2 = tempMin2;
            prevColor = tempColor;
        }
        
        return prevMin1;
    }

---

从3个颜色换成K个了。

按上一题的思路走，就是维护K个结果，最后再选。

但是做起来谈何容易。。。

N个房子，每一步都要算K个结果(K-1个)，然后每个结果都要比较(k-1)里面最小的，最终是n * k * k

说O(nk)的解法。

维护2个量，当前最小，当前第二小。。这种思路一般是不行的，但是此题是非一即二，只能和前面颜色相同或者不同，所以维护2个是可以的。

如果和前面颜色不同，我们就选当前最小；相同就退而求其次，选第二小，不可能既和前一个颜色相同，又不同。

所以需要记录2个最小量，还要记录前一层是啥鸡巴颜色，每次的值要先和最小的比较，再和第二小的比较，维护两个量。

最终结果是最小的。

public class Solution {
    public int minCostII(int[][] costs) {
        if (costs.length == 0) return 0;
        
        int prevColor = -1;
        int min1 = 0;
        int min2 = 0;
        for (int i = 0; i < costs.length; i++) {
            
            int prevMin1 = Integer.MAX_VALUE;
            int prevMin2 = Integer.MAX_VALUE;
            int tempColor = -1;
            
            for (int j = 0; j < costs[i].length; j++) {
                int temp = 0;
                
                // local min cost
                if (j != prevColor) {
                    temp = min1;
                } else {
                    temp = min2;
                }
                temp += costs[i][j];
                
                // if this localMin is also global?
                if (temp < prevMin1) {
                    prevMin2 = prevMin1;
                    prevMin1 = temp;
                    tempColor = j;
                } else if (temp < prevMin2) {
                    prevMin2 = temp;
                }
            }
            
            // update
            prevColor = tempColor;
            min1 = prevMin1;
            min2 = prevMin2;
        }
        
        return min1;
    }
}