Paint House II -- DP -- Leetcode

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.

Note:
All costs are positive integers.

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

Answer:

1. Basic: Time: O(n * k * k), Space: O(1)

public int minCostII(int[][] costs) {

        if(costs==null)return 0;

        int n = costs.length;

        if(n==0)return 0;

        if(costs[0]==null)return 0;

        int k = costs[0].length;

        if(k==0)return 0;

        

        //Time: O(n*k*k)

        for(int i=1;i<n;++i){

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

                 int min = Integer.MAX_VALUE;

                 for(int w=0;w<k;++w){

                    if(w!=j){

                        min = Math.min(costs[i-1][w], min);

                    }

                 }

                 costs[i][j] += min;

            }

        int res = Integer.MAX_VALUE;

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

            res = Math.min(res, costs[n-1][j]);

        }

        return res;

}

2. Followup: Time: O(n * k), Space: O(1)

public int minCostII(int[][] costs) {

        if(costs==null)return 0;

        int n = costs.length;

        if(n==0)return 0;

        if(costs[0]==null)return 0;

        int k = costs[0].length;

        if(k==0)return 0;

        

        for(int i=1;i<n;++i){

            //Time: O(n * k)

            int min1 = Integer.MAX_VALUE;

            int min2 = min1;

            int minIndex1 = -1;

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

                if(costs[i-1][j] < min1){

                    min2 = min1;

                    min1 = costs[i-1][j];

                    minIndex1 = j;

                }else if(costs[i-1][j] >= min1 && costs[i-1][j] < min2){

                    min2 = costs[i-1][j];

                }

            }

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

               if(j == minIndex1){

                   costs[i][j] += min2;

               }else{

                   costs[i][j] += min1;

               }

            }

        }

        

        int res = Integer.MAX_VALUE;

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

            res = Math.min(res, costs[n-1][j]);

        }

        return res;

}