256 & 265. Paint House

https://leetcode.com/problems/paint-house/description/

状态定义 minCost[i][j] means 第 i 处房子，选择 color j 的最小 cost
状态转移方程: minCost[i][red] = min(minCost[i-1][blue], minCost[i-1][green]) + costs[i][red]
初始化: int[][] minCost = new int[costs.length + 1][colors count]
循环体
返回 target: min(minCost[len][3 colors])
优化： 两个一维数组做 dp 就ok了，因为第 i 处房子 minCost，只与第 i - 1 处房子相关。

class Solution {    
    public int minCost(int[][] costs) {
        if (costs == null || costs.length == 0 || costs[0] == null || costs[0].length == 0) {
            return 0;
        }
        
        int rows = costs.length;
        int cols = costs[0].length;
        int[][] minCosts = new int[rows + 1][cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int lastMin = Integer.MAX_VALUE;
                for (int jj = 0; jj < cols; jj++) {
                    if (jj != j) {
                        lastMin = Math.min(lastMin, minCosts[i][jj]);
                    }
                }
                minCosts[i + 1][j] = lastMin + costs[i][j];
            }
        }
        
        int minFinal = Integer.MAX_VALUE;
        for (int j = 0; j < cols; j++) {
            minFinal = Math.min(minFinal, minCosts[rows][j]);
        }
        return minFinal;
    }
}

Follow Up: K 个color

https://leetcode.com/problems/paint-house-ii/description/

上面的题解已经实现了 K 个 color，只是有一个 Corner case: k == 1; 那么对应的房子数目不可以超过1个。这种情况直接返回就好了。

// only 1 color
int cols = costs[0].length;
if (cols == 1) {
    return costs[0][0];
}

该 Solution 为 O(n * k^2), 将其优化为 O(n * k) 的思路如下：

可以记录 i 处，非某一 color 的 minCost
例如在 i 处， minCosts 为 Red-3， Blue-5，Green-2，Pink-7
那么，在 i 处，minCosts NotRed-2, NotBlue-2, NotGreen-3, NotPink-2
即 找到最小的两个值对应的 Color，如果最小的两个值相等，则 NotColor 均为最小值；otherwise, 最小值 Green 对应的 NotColor 为 second minimal cost，其他为 minimal cost。