Paint House II 516

Question

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.

Notice

All costs are positive integers.

Example

Given n = 3, k = 3, costs = [[14,2,11],[11,14,5],[14,3,10]] return 10

house 0 is color 2, house 1 is color 3, house 2 is color 2, 2 + 5 + 3 = 10

Challenge

Could you solve it in O(nk)?

Solution

这道题思路和I十分相似，不同的是颜色变为k种，若还是按照I中的方法，更新当前行的某个值时需要搜索上一行和当前不同列的所有可能，则当k很大时，会十分耗费时间。因此，可以不能直接用I中的方法，需要优化。

优化的方法为：

1. 只记录3个值，即前一行最小值，第二小值，和最小值的index。

2. 更新当前行元素，当前行元素记录的是当前行房子涂该种颜色时的最小值，只可能由该元素与上一行的最小值或次小值加和得到。遍历当前行的每个元素，若该元素的列和前一行最小值index不同，则更新为当前行元素值＋上一行最小值，若和上一行最小值index相同，则更新为当前元素值＋上一行次小值。同时将该值和当前行的最小值和次小值比较，更新当前行的最小值，次小值和最小值的index。

3. 重复2直到遍历所有行。

时间O(N=nk)，空间O(1)。

代码如下：

public class Solution {
    /**
     * @param costs n x k cost matrix
     * @return an integer, the minimum cost to paint all houses
     */
    public int minCostII(int[][] costs) {
        // Write your code here
        if(costs == null || costs.length == 0 || costs[0].length == 0){
            return 0;
        }

        int n = costs.length;
        int k = costs[0].length;

        int preLeast = 0;
        int preSecond = 0;
        int preIndex = -1;
        for(int i = 0; i < n; i++){
            int curtLeast = Integer.MAX_VALUE;
            int curtSecond = Integer.MAX_VALUE;
            int curtIndex = -1;
            for(int j = 0; j < k; j++){
                if(j == preIndex){
                    costs[i][j] += preSecond;
                }else{
                    costs[i][j] += preLeast;
                }
                //更新最小值，次小值，最小值index
                if(costs[i][j] < curtLeast){
                    curtSecond = curtLeast;
                    curtLeast = costs[i][j];
                    curtIndex = j;
                }else if(costs[i][j] < curtSecond){
                    curtSecond = costs[i][j];
                }
            }
            preLeast = curtLeast;
            preSecond = curtSecond;
            preIndex = curtIndex;
        }

        return preLeast;
    }
}