求lc Paint House II的O(nk)解法

求地里大神能给一下解答，目前小弟只想到用DP的解法但是复杂度是O(nk^2), 目前能想到的改进成nk的方法是用bucket sort，但是太渣，不会写桶排序，求大神指导

一天了，没人回复。。。。

DP为啥是O(nk^2)? 难道不是O(nk)?

public int minCostII(int[][] costs){
                if(costs == null || costs.length == 0 || costs[0].length <= 1){
                        return 0;
                }
                int k = costs.length;
                int n = costs[0].length;
                int firstIndex = -1;
                int first = 0;
                int second = 0;
                for(int i=1;i<n;i++){
                        int newFirst = Integer.MAX_VALUE;
                        int newSecond = Integer.MAX_VALUE;
                        int newFirstIndex = -1;
                        for(int j=0;j<k;j++){
                                int cur = costs[j][i];
                                costs[j][i] = cur + (firstIndex == j? second:first);
                                if(costs[j][i] < newFirst){
                                        newSecond = newFirst;
                                        newFirst = costs[j][i];
                                        newFirstIndex = j;
                                }
                                else if(costs[j][i] < newSecond){
                                        newSecond = costs[j][i];
                                }
                        }
                        first = newFirst;
                        firstIndex = newFirstIndex;
                        second = newSecond;
                }
                return first;
        }
写了一个，因为没有买premium，所以不知道能不能AC，只是提供一下自己的思路，也不知道对不对，求讨论。
用DP，如果不能改变costs[][]的值,就新create一个matrix，cost[j][i]表示第i个房子刷第k种颜色，前i个房子最少的cost，记录firstIndex是为了满足相邻房子不能刷同种颜色的条件。
可能会有bug，

宝贝忆彼岸 发表于 2015-8-21 08:23
public int minCostII(int[][] costs){
                if(costs == null || costs.length == 0 || costs[0].length

复杂度是多少？nk？

jiebour 发表于 2015-8-21 08:39
复杂度是多少？nk？

是的 字。。。。。。。数