LeetCode: 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.

// Follow up:
// Could you solve it in O(nk) runtime?
/**
Ref: http://buttercola.blogspot.com/2015/09/leetcode-paint-house-ii.html

Let us assume, we have "min_1" and "min_2".
min_1 : the lowest cost at previous stage.
min_2 : the 2nd lowest cost at previous stage.

And we have the minimum costs for all colors at previous stage.
color[i-1][k]

Then, iff we decide to paint house "i" with color "j", we can compute the minimum cost of other colors at "i-1" stage through following way.
case 1: iff "color[i-1][j] == min_1", it means the min_1 actually records the minimum value of color[i-1][j] (previous color is j), we have to use min_2;
case 2: iff "color[i-1][j] != min_1", it means min_1 is not the value of color[i-1][j] (previous color is not j), we can use the min_1's color.
Note: iff "pre_min_1 == pre_min_2", it means there are two minimum costs, anyway, no matter which color is pre_min_1, we can use pre_min_2.
----------------------------------------------------------
if (dp[j] != pre_min_1 || pre_min_1 == pre_min_2) {
    dp[j] = pre_min_1 + costs[i][j];
} else{
    dp[j] = pre_min_2 + costs[i][j];
}
----------------------------------------------------------
The way to maintain "min_1" and "min_2".
for (int i = 0; i < len; i++) {
    ...
    min_1 = Integer.MAX_VALUE;
    min_2 = Integer.MAX_VALUE;
    ...
    if (dp[j] <= min_1) {
        min_2 = min_1;
        min_1 = dp[j];
    } else if (dp[j] < min_2){
        min_2 = dp[j];
    }
}
*/
public class PaintHouseII {
    public int minCostII(int[][] costs) {
        if(costs == null|| costs.length == 0) {
            return 0;
        }
     
        int m = costs.length;
        int n = costs[0].length;
     
        int min1 = -1;
        int min2 = -1;
     
        for(int i = 0; i < m; i++) {
            int last1 = min1;
            int last2 = min2;

            min1 = -1;
            min2 = -1;
         
            for(int j = 0; j < n; j++) {
                if(j != last1) {
                    costs[i][j] += last1 < 0 ? 0 : costs[i - 1][last1];
                } else {
                    costs[i][j] += last2 < 0 ? 0 : costs[i - 1][last2];
                }

                if(min1 < 0 || costs[i][j] < costs[i][min1]) {
                    min2 = min1;
                    min1 = j;
                } else if(min2 < 0 || costs[i][j] < costs[i][min2]) {
                    min2 = j;
                }
            }
        }
     
        return costs[m - 1][min1];     
    }
}