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.

All costs are positive integers.

Example

Example 1

Input:
costs = [[14,2,11],[11,14,5],[14,3,10]]
Output: 10
Explanation:
The three house use color [1,2,1] for each house. The total cost is 10.

Example 2

Input:
costs = [[5]]
Output: 5
Explanation:
There is only one color and one house.

Challenge

Could you solve it in O(nk)?

public class Solution {
    public int minCostII(int[][] costs) {
        if(costs.length==0||costs==null)
            return 0;
        Integer[][] dp = new Integer[costs.length][costs[0].length];
        int min = Integer.MAX_VALUE, secondMin = Integer.MAX_VALUE;
        int minColor = -1;
        for (int i = 0; i < costs[0].length; i++) {
            dp[0][i] = costs[0][i];
            if (costs[0][i] < min) {
                secondMin = min;
                min = costs[0][i];
                minColor = i;
            } else if (costs[0][i] < secondMin)
                secondMin = costs[0][i];
        }
        for (int i = 1; i < costs.length; i++) {
            int newMin = Integer.MAX_VALUE, newSecond = Integer.MAX_VALUE;
            int newColor = -1;
            for (int j = 0; j < costs[i].length; j++) {
                // If it is same as previous color(which holds min value)
                if (j == minColor)
                    dp[i][j] = costs[i][j] + secondMin;
                else
                    dp[i][j] = costs[i][j] + min;
                if (dp[i][j] < newMin) {
                    newSecond = newMin;
                    newMin = dp[i][j];
                    newColor = j;
                } else if (dp[i][j] < newSecond)
                    newSecond = dp[i][j];
            }
            min = newMin;
            secondMin = newSecond;
            minColor = newColor;
        }
        return min;
    }
}