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.

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)?

Key Points: O(nk) O(1)

1. Optimization: Since every state f(i,C) only depends on f(i-1, 0-k ), so we just need O(k) to store the last state and compute the current one.
2. Further more: Since we just need the max value from f(i-1, 0-k), So O(1) is totally possible.
3. Formula:

          f(i,c) = max( 
                        f(i-1,C0)+A[i][c],
                        f(i-1,C1)+A[i][c],
                        .....
                        f(i-1,Ck)+A[i][c]
                     ) (Cn!=c)

    public int minCostII(int[][] costs) {
        if(costs.length==0||costs[0].length==0){return 0;}

        int n = costs.length, k=costs[0].length;
        int[] lastState = new int[2], currentState = new int[2],
        lastColor = new int[2],currentColor=new int[2];
        // initilizatino
        Arrays.fill(lastState,0);
        Arrays.fill(lastColor,-1);
        Arrays.fill(currentState,Integer.MAX_VALUE);
        Arrays.fill(currentColor,0);



        for(int i=0; i<n; i++){
            for(int j=0; j<k; j++){
                int temp=0;

                // calculate the minimum cost for current color
                if(j!=lastColor[0]){
                    temp=lastState[0]+costs[i][j];
                }else{
                    temp=lastState[1]+costs[i][j];
                }

                // set the smallest and the second smallest cost/color in current state
                if(temp<currentState[0]){
                      currentState[1]=currentState[0];
                        currentColor[1]=currentColor[1];
                        currentState[0]=temp;
                        currentColor[0]=j;

                    }else if(temp<currentState[1]){
                        currentState[1]=temp;
                        currentColor[1]=j;
                    }
            }

            // override lastState with currentState and reset currenState
            lastState[0] = currentState[0];
            lastState[1] = currentState[1];
            lastColor[0] = currentColor[0];
            lastColor[1] = currentColor[1];
            Arrays.fill(currentState,Integer.MAX_VALUE);
        }
        return lastState[0];
    }