Paint House

The basic idea of this approach is to break the original problem into sub-problems. We will try to check each valid way of painting the houses. And, then find the minimum cost.

 Now, let us define a recursive function 

getMinCost(int i, int j)

Which returns the minimum cost to paint the first ‘i’ houses (0-th based indexing) such that the last house (i-th house) is painted with j-th colour.

 Algorithm

• Base Case:
  • If i == -1, then return 0. It denotes that we don’t have any house to paint so the cost will be 0.
• Now, if we are choosing to paint the i-th house with j-th colour then we can’t paint the (i - 1)-th house with j-th colour. Create a variable “ans” which will store the answer to the current sub-problem and initialise it with a very large integer.
• Start traversing through the possible colours using a variable ‘k’.
  • If (j != k) then we can choose the k-th colour to paint the (i - 1)-th house. Therefore, ans = min(ans, cost[i][j] + getMinCost(i - 1, k))
• Return the “ans”.

Let us observe the recursion tree for the first test case of sample test 2.

After observing the tree, we’ll find that there are some redundant function calls which means that there are some overlapping subproblems. The repetition of such sub-problems suggests that we can use dynamic programming to optimize our approach.

 The key idea behind a dynamic programming approach is to use memoization, i.e. we’ll save the result of our sub-problem in a matrix so that it can be used later on.

 Let dp[ i ][ j ] be our dynamic programming matrix of N * 3 dimensions to store the minimum cost to paint first ‘i’ houses such that the i-th house is painted with j-th colour.

 Now, consider the following steps to implement the getMinCost(int i, int j) function along with memoization :

• Base Case:
  • If i == -1, then return 0. It denotes that we don’t have any house to paint so the cost will be 0.
• Check if the answer for this sub-problem already exists in the “dp” matrix i.e. dp[i][j] is not equal to -1. If it exists, then return it right away.
• Now, if we are choosing to paint the i-th house with j-th colour then we can’t paint the (i - 1)-th house with j-th colour. Create a variable “ans” which will store the answer to the current sub-problem and initialise it with a very large integer.
• Start traversing through the possible colours using a variable ‘k’.
  • If (j != k) then we can choose the k-th colour to paint the (i - 1)-th house. Therefore, ans = min(ans, cost[i][j] + getMinCost(i - 1, k))
• Store the “ans” into dp[i][j] to avoid redundant function calls.
• Return “ans”.

The basic idea of this approach is to solve the problem iteratively.

 Let dp[ i ][ j ] be our dynamic programming matrix of N * 3 dimensions to store the minimum cost to paint first ‘i’ houses such that the i-th house is painted with j-th colour.

 Algorithm

• Initialize the “dp” matrix for the first house i.e. dp[0][0] = cost[0][0], dp[0][1] = cost[0][1], dp[0][2] = cost[0][2]
• Start traversing the houses using a variable ‘i’ such that 1 <= ‘i’ < N
• Now, let’s see the possible options for painting the current house.
  • If the chosen colour is 0, then the (i - 1)-the house should be painted with colour 1 or colour 2. Therefore, dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0]
  • If the chosen colour is 1, then the (i - 1)-the house should be painted with colour 0 or colour 2. Therefore, dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1]
  • If the chosen colour is 2, then the (i - 1)-the house should be painted with colour 0 or colour 1. Therefore, dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2]
• Now, the minimum value among dp[N-1][0], dp[N-1][1], dp[N-1][2] will be the minimum cost to paint the ‘N’ houses while following the given constraints.

We can observe in approach 3 that the current state depends on one immediate previous house. This suggests we can use three variables to store the cost of painting the previous house with given colors.

 Let “lastGreen”, “lastRed” and “lastYellow” be three variables that store the cost if the last house is painted with green, red and yellow color, respectively.

 Algorithm

• Initialize all the three variables for the first house i.e. lastGreen = cost[0][0], lastRed = cost[0][1], lastYellow = cost[0][2]
• Start traversing the houses using a variable ‘i’ such that 1 <= ‘i’ < N
• Let’s see the possible options of painting the current house.
  • Let “curGreen”, “curRed” and “curYellow” be three variables which store the cost if the current house is painted with green, red and yellow, respectively.
  • If the chosen colour is green, then the (i - 1)-the house should be painted with red or yellow. Therefore,  curGreen = min(lastRed, lastYellow) + cost[i][0]
  • If the chosen colour is red, then the (i - 1)-the house should be painted green or yellow. Therefore, curRed = min(lastGreen, lastYellow) + cost[i][1]
  • If the chosen colour is yellow, then the (i - 1)-the house should be painted green or red. Therefore, curYellow = min(lastGreen, lastRed) + cost[i][2]
  • Now, copy the current values into the last ones.
• Now, the minimum value among “lastGreen”, “lastRed”, “lastYellow” will be the minimum cost to paint the ‘N’ houses while following the given constraints.