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.

Example:

Input: [[1,5,3],[2,9,4]]
Output: 5
Explanation: Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5; 
             Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5. 

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

My answer:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

class Solution { public int minCostII(int[][] costs) { // Solution 1: O(n*k^2) time, space O(nk) // dp[n][k] // dp[i][0] min cost given color0 is painted to ith house // dp[i][1] min cost given color1 is painted to ith house // dp[i][2] min cost given color2 is painted to ith house // if (costs == null || costs.length == 0) { // return 0; // } // int[][] dp = new int[costs.length][costs[0].length]; // for (int i = 0; i < costs[0].length; i ++) { // dp[0][i] = costs[0][i]; // } // for (int i = 1; i < costs.length; i ++) { // for (int j = 0; j < costs[i].length; j ++) { // int minValidPreCost = Integer.MAX_VALUE; // for (int k = 0; k < costs[i].length; k ++) { // if (j == k) { // continue; // } // minValidPreCost = Math.min(minValidPreCost, dp[i-1][k]); // } // dp[i][j] = costs[i][j] + minValidPreCost; // } // } // int minCost = Integer.MAX_VALUE; // for (int i = 0; i < dp[costs.length - 1].length; i ++) { // minCost = Math.min(minCost, dp[costs.length - 1][i]); // } // return minCost; // Solution 2: only keep track of second min and min of previous row // because each time we only add min/second min to current row // second min is only for index of min // time O(nk), space is O(1) if (costs == null || costs.length == 0) { return 0; } int preMin = -1; int preSecondMin = -1; int preMinIdex = -1; for (int i = 0; i < costs[0].length; i ++) { if (preMin == -1 || costs[0][i] < preMin) { preSecondMin = preMin; preMin = costs[0][i]; preMinIdex = i; } else if (preSecondMin == -1 || costs[0][i] < preSecondMin) { preSecondMin = costs[0][i]; } } for (int i = 1; i < costs.length; i ++) { int currentMin = -1; int currentSecondMin = -1; int currentMinIndex = 0; for (int j = 0; j < costs[i].length; j ++) { int currentCost = costs[i][j]; if (j != preMinIdex) { currentCost += preMin; } else { currentCost += preSecondMin; } if (currentMin == -1 || currentCost < currentMin) { currentSecondMin = currentMin; currentMin = currentCost; currentMinIndex = j; } else if (currentSecondMin == -1 || currentCost < currentSecondMin) { currentSecondMin = currentCost; } } preMin = currentMin; preSecondMin = currentSecondMin; preMinIdex = currentMinIndex; } return preMin; } }