265. Paint House II

Description

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a *n* x *k* cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Example:

Input: [[1,5,3],[2,9,4]]
Output: 5
Explanation: Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5;
Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5.

Follow up:
Could you solve it in O(nk) runtime?

Solution

DP, O(nk), S(nk)

这道题的思路就是在"Paint House"基础上进行扩展，将3维扩展到k维上，时间复杂度为O(n * k ^ 2)。

想降低时间复杂度也很简单，只要优化getMinExcept(int[] nums, int exceptIndex)即可。方法是预处理，记录minIndex和secondMinIndex。

class Solution {
    public int minCostII(int[][] costs) {
        if (costs == null || costs.length == 0 || costs[0].length == 0) {
            return 0;
        }
        
        int n = costs.length;
        // imporant to handle it here or getMinIndex might return -1
        if (n == 1) {   
            return min(costs[0]);
        }
        
        int k = costs[0].length;
        int[][] costSum = new int[n + 1][k];
        
        for (int i = 0; i < n; ++i) {
            int[] arr = getFirstAndSecondMinIndexes(costSum[i]);
            
            for (int j = 0; j < k; ++j) {
                costSum[i + 1][j] = costs[i][j] 
                    + (j != arr[0] 
                            ? costSum[i][arr[0]] : costSum[i][arr[1]]);
            }
        }
        
        return min(costSum[n]);
    }
    
    private int[] getFirstAndSecondMinIndexes(int[] nums) {
        int[] res = new int[2];
        Arrays.fill(res, -1);
        
        for (int i = 0; i < nums.length; ++i) {
            if (res[0] < 0 || nums[i] <= nums[res[0]]) {
                res[1] = res[0];
                res[0] = i;
            } else if (res[1] < 0 || nums[i] < nums[res[1]]) {
                res[1] = i;
            }
        }
        
        return res;
    }
    
    private int min(int[] nums) {
        int min = Integer.MAX_VALUE;
        
        for (int n : nums) {
            min = Math.min(n, min);
        }
        
        return min;
    }
}

DP, O(nk), S(1)

可以将costs的值做修改，改成costSum。这样就不需要新开辟空间啦。

注意一些edge case的处理，例如[[1],[3]]这种，不可能fill成功的，直接返回MAX_VALUE。否则运行到后面min1一直为-1，会抛IndexOutOfBoundException。

class Solution {
    public int minCostII(int[][] costs) {
        if (costs == null || costs.length == 0 || costs[0].length == 0) {
            return 0;
        }
        
        int n = costs.length;
        int k = costs[0].length;
        if (n > 1 && k < 2) {
            return Integer.MAX_VALUE;   // impossible to fill
        }
        
        int min0 = -1;
        int min1 = -1;
        
        for (int i = 0; i < n; ++i) {
            int currMin0 = -1;
            int currMin1 = -1;
            
            for (int j = 0 ; j < k; ++j) {
                if (i > 0) {
                    costs[i][j] += min0 != j 
                        ? costs[i - 1][min0] : costs[i - 1][min1];
                }
                
                if (currMin0 < 0 || costs[i][j] < costs[i][currMin0]) {
                    currMin1 = currMin0;
                    currMin0 = j;
                } else if (currMin1 < 0 
                           || costs[i][j] < costs[i][currMin1]) {
                    currMin1 = j;
                }
            }
            
            min0 = currMin0;
            min1 = currMin1;
        }
        
        return costs[n - 1][min0];
    }
}