1
class Solution {
2
  public int helper(
3
      int idx, int[] houses, int[][] cost, int target, int prevColor, int neigh, Integer[][][] dp) {
4
    if (idx == houses.length || neigh > target) {
5
      if (neigh == target) return 0;
6
      return Integer.MAX_VALUE;
7
    }
8
    if (dp[idx][prevColor][neigh] != null) return dp[idx][prevColor][neigh];
9
    int minCost = Integer.MAX_VALUE;
10

11
    if (houses[idx] == 0) {
12
      for (int j = 0; j < cost[idx].length; j++) {
13
        int minCostHere = Integer.MAX_VALUE;
14

15
        if (j + 1
16
            == prevColor) // Painting the house with the same colour as that of the previous one.
17
        minCostHere = helper(idx + 1, houses, cost, target, prevColor, neigh, dp);
18
        else // Painting the house with a different color and incrementing the neighbour count.
19
        minCostHere = helper(idx + 1, houses, cost, target, j + 1, neigh + 1, dp);
20

21
        if (minCostHere != Integer.MAX_VALUE) minCostHere += cost[idx][j];
22

23
        minCost = Math.min(minCostHere, minCost);
24
      }
25
    } else {
26
      if (houses[idx] == prevColor)
27
        minCost = helper(idx + 1, houses, cost, target, prevColor, neigh, dp);
28
      else minCost = helper(idx + 1, houses, cost, target, houses[idx], neigh + 1, dp);
29
    }
30

31
    return dp[idx][prevColor][neigh] = minCost;
32
  }
33

34
  public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
35

36
    Integer[][][] dp = new Integer[m][n + 1][target + 1];
37
    int ans = helper(0, houses, cost, target, 0, 0, dp);
38
    return ans == Integer.MAX_VALUE ? -1 : ans;
39
  }
40
}