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?

Solution:

  1. public class Solution {
  2.   public int minCostII(int[][] costs) {
  3.     if (costs == null || costs.length == 0) return 0;
  5.     int n = costs.length, k = costs[0].length;
  6.     // min1 is the index of the 1st-smallest cost till previous house
  7.     // min2 is the index of the 2nd-smallest cost till previous house
  8.     int min1 = -1, min2 = -1;
  10.     for (int i = 0; i < n; i++) {
  11.       int last1 = min1, last2 = min2;
  12.       min1 = -1; min2 = -1;
  14.       for (int j = 0; j < k; j++) {
  15.         if (j != last1) {
  16.           costs[i][j] += last1 < 0 ? 0 : costs[i - 1][last1];
  17.         } else {
  18.           costs[i][j] += last2 < 0 ? 0 : costs[i - 1][last2];
  19.         }
  21.         if (min1 < 0 || costs[i][j] < costs[i][min1]) {
  22.           min2 = min1; min1 = j;
  23.         } else if (min2 < 0 || costs[i][j] < costs[i][min2]) {
  24.           min2 = j;
  25.         }
  26.       }
  27.     }
  29.     return costs[n - 1][min1];
  30.   }
  31. }