Paint House II

题目
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?

答案
直接改编Paint House题的答案

O(nk^2)

class Solution {
    public int minCostII(int[][] costs) {
        if(costs.length == 0) return 0;
        int n = costs.length, k = costs[0].length;
        int[][] dp = new int[n][k];
        
        // dp[i][j] means the min cost of painting houses i to n - 1, if I painted house i with color j
        // If we successfully fill this dp array, then answer to this problem is min(dp[0][0:k])
        // Let's fill in the base cases first
        
        // For the last house, if we want to paint it with red color, then the min cost is obviously costs[n-1][0]
        // Same for blue and green
        for(int i = 0; i < k; i++) {
            dp[n - 1][i] = costs[n - 1][i];
        }        
        
        // Now we consider how to calculate dp[i] based on dp[i+1]
        // If we know what's stored in dp[i+1] are the minimum cost, then making optimal decision for dp[i] is easy
        // For example, if we want to paint house i as red, then 
        // dp[i][RED] = cost of painiting house i with red color + minimum cost of painting remaining house with any color
        // = cost of painiting house i with red color + min(dp[i+1][BLUE], dp[i+1][GREEN])
        int res = Integer.MAX_VALUE;
        for(int i = n - 2; i >= 0; i--) {
            for(int j = 0; j < k; j++) {
                int min = Integer.MAX_VALUE;
                for(int p = 0; p < k; p++) {
                    if(p == j) continue;
                    min = Math.min(min, dp[i + 1][p]);
                }
                dp[i][j] = costs[i][j] + min;
            }
        }
        
        for(int i = 0; i < k; i++) {
            res = Math.min(res, dp[0][i]);
        }
        return res;
    }
}

Optimized code:
O(nk)

class Solution {
    public int[] findMin(int[] arr) {
        int min = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        for(int i = 0; i < arr.length; i++) {
            if(arr[i] <= min){
                min2 = min;
                min = arr[i];
            } 
            else if(arr[i] <= min2){
                min2 = arr[i];
            }
        }
        return new int[]{min, min2};
    }
    public int minCostII(int[][] costs) {
        if(costs.length == 0) return 0;
        int n = costs.length, k = costs[0].length;
        int[][] dp = new int[n][k];
        
        // dp[i][j] means the min cost of painting houses i to n - 1, if I painted house i with color j
        // If we successfully fill this dp array, then answer to this problem is min(dp[0][0:k])
        // Let's fill in the base cases first
        
        // For the last house, if we want to paint it with red color, then the min cost is obviously costs[n-1][0]
        // Same for blue and green
        for(int i = 0; i < k; i++) {
            dp[n - 1][i] = costs[n - 1][i];
        }        
        
        // Now we consider how to calculate dp[i] based on dp[i+1]
        // If we know what's stored in dp[i+1] are the minimum cost, then making optimal decision for dp[i] is easy
        // For example, if we want to paint house i as red, then 
        // dp[i][RED] = cost of painiting house i with red color + minimum cost of painting remaining house with any color
        // = cost of painiting house i with red color + min(dp[i+1][BLUE], dp[i+1][GREEN])
        int res = Integer.MAX_VALUE;
        for(int i = n - 2; i >= 0; i--) {
            // Optimization: lets find the smallest value and 2ed smallest value
            // If the value we're excluding is the smallest one, then use 2ed smallest
            // Otherwise, the minimum value is always the smallest
            int[] min = findMin(dp[i + 1]);
            int minimum;
            for(int j = 0; j < k; j++) {
                if(dp[i + 1][j] == min[0]) minimum = min[1];
                else minimum = min[0];
                dp[i][j] = costs[i][j] + minimum;
            }
        }
        
        for(int i = 0; i < k; i++) {
            res = Math.min(res, dp[0][i]);
        }
        return res;
    }
}