265. 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?

一刷
题解：这题如果不用长度为k的DP的话，方法是，保存cost最小的两个颜色的index, 因为如果cost最小和当前颜色相同，就取第二小。

public class Solution {
    public int minCostII(int[][] costs) {
        if (costs == null || costs.length == 0) return 0;
        
        //n: number of house, k: number of color
        int n = costs.length, k = costs[0].length; 
        int min1 = -1, min2 = -1;
        
        for(int i=0; i<n; i++){//house
            int last1 = min1, last2 = min2;
            min1 = -1;
            min2 = -1;
            for(int j=0; j<k; j++){//color
                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[n-1][min1];
    }
}