Reference: LeetCode
Difficulty: Easy

Twitter OA 2019 | Coloring the blocks

My Post: [Java] Dynamic Programming is Cool (Explanation)

Problem

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. 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 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

Note: All costs are positive integers.

Example: 

1
2
3
4
5
Input: [[17,2,17],[16,16,5],[14,3,19]]
Output: 10

Input: []
Output: 0

Analysis

DP

  • Define: dp[i][j] is the minimum cost of painting i-th house with color j.
  • Recurrence: (3 states)
    • dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i][0]
    • dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1]
    • dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][2]
  • Init:
    • dp[0][0] = cost[i][0]
    • dp[0][1] = cost[i][1]
    • dp[0][2] = cost[i][2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int minCost(int[][] costs) {
  if (costs == null || costs.length == 0) return 0;
  // Assume all costs are positive
  int n = costs.length; // number of houses
  int[][] dp = new int[n][3];
  // Init
  dp[0][0] = costs[0][0];
  dp[0][1] = costs[0][1];
  dp[0][2] = costs[0][2];
  // DP
  for (int i = 1; i < n; ++i) {
    dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
    dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];
    dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2];
  }
  return Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2]));
}

Time: $O(N)$
Space: $O(N)$