Leetcode - Paint House II

My code:

public class Solution {
    public int minCostII(int[][] costs) {
        if (costs == null || costs.length == 0 || costs[0].length == 0) {
            return 0;
        }
        int min1 = -1;
        int min2 = -1;
        int k = costs[0].length;
        int n = costs.length;
        for (int i = 0; i < n; i++) {
            int lastMin1 = min1;
            int lastMin2 = min2;
            min1 = -1;
            min2 = -1;
            
            for (int j = 0; j < k; j++) {
                if (j != lastMin1) {
                    costs[i][j] += (lastMin1 < 0 ? 0 : costs[i - 1][lastMin1]);
                }
                else {
                    costs[i][j] += (lastMin2 < 0 ? 0 : costs[i - 1][lastMin2]);
                }
                
                if (min1 == -1 || costs[i][j] < costs[i][min1]) {
                    min2 = min1;
                    min1 = j;
                }
                else if (min2 == -1 || costs[i][j] < costs[i][min2]) {
                    min2 = j;
                }
            }
        }
        
        return costs[n - 1][min1];            
    }
}

reference:
https://discuss.leetcode.com/topic/22580/ac-java-solution-without-extra-space/2

继续是贪心的思想。
我一开始并不是这么做的，用了自己的做法，并且AC
在 I 中，是三个房子，我用了三个变量来存上一层。
所以这一题，我首先想到的就是，用 k 个变量，形成一个list，来存上一层。

于是写了下面代码：
My code:

public class Solution {
    public int minCostII(int[][] costs) {
        if (costs == null || costs.length == 0 || costs[0].length == 0) {
            return 0;
        }
        List<Integer> last = new ArrayList<Integer>();
        for (int i = 0; i < costs[0].length; i++) {
            last.add(costs[0][i]);
        }
        
        for (int i = 1; i < costs.length; i++) {
            List<Integer> curr = new ArrayList<Integer>();
            for (int j = 0; j < last.size(); j++) {
                curr.add(getMin(j, last) + costs[i][j]);
            }
            last = curr;
        }
        
        return getMin(-1, last);
    }
    
    private int getMin(int excludeIndex, List<Integer> list) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < list.size(); i++) {
            if (i == excludeIndex) {
                continue;
            }
            else {
                min = Math.min(min, list.get(i));
            }
        }
        return min;
    }
}

AC
但是空间复杂度是 O(k)
而且，从链表中读写，也都需要消耗时间。

于是看了答案。发现自己对这道题目的认识还是不够深刻。
为什么要存 k 个变量呢？
我们要求最小值。那么， k 个变量都会对最终结果产生影响吗？
当然不会。
只有最小的两个，他们会对下一层结果产生结果。
或者说，下一层结果的最小值，一定是由这两个最小值决定的。

于是每一层只用两个变量来存下当前这一层，最小的两个cost的index

为什么是两个？
当我们遍历 [0, k - 1] 时，可能某个index = min1
所以这个时候我们不能用这个颜色。为了达到最小的结果。我们得存一个 min2

思路差不多就这样了。

然后一个小细节。
如何保存最小的两个变量呢？

int min1 = -1;
int min2 = -1
for (int j = 0; j < k; j++) {
    if (min1 < 0 || costs[i][j] < costs[i][min1]) {
        min2 = min1;
        min1 = j;
    }
    else {
        min2 = j;
    }
}

注意第一个if里面加的 min2 = min1;
缺了他不可。

Anyway, Good luck, Richardo! -- 09/20/2016