1
class Solution {
2
  int dp[101][22][101];
3
  vector<int> h;         // m
4
  vector<vector<int>> c; // n
5
  int mm;
6
  int nn;
7
  int t;
8
  int dfs(int idx, int prev, int curt) {
9
    if (curt < 1) return INT_MAX;
10
    if (idx == mm) return (curt == 1) ? 0 : INT_MAX;
11
    if (dp[idx][prev][curt] != -1) return dp[idx][prev][curt];
12
    int res = INT_MAX;
13
    int color = h[idx];
14
    if (color == 0) {
15
      for (int x = 0; x < nn; x++) {
16
        color = x + 1;
17
        int rres = dfs(idx + 1, color, curt - (prev != 21 and prev != color));
18
        if (rres != INT_MAX) res = min(c[idx][color - 1] + rres, res);
19
      }
20
    } else {
21
      return dp[idx][prev][curt] = dfs(idx + 1, color, curt - (prev != 21 and prev != color));
22
    }
23
    return dp[idx][prev][curt] = res;
24
  }
25

26
 public:
27
  int minCost(vector<int> &houses, vector<vector<int>> &cost, int m, int n, int target) {
28
    h = houses, c = cost, mm = m, nn = n, t = target;
29
    memset(dp, -1, sizeof(dp));
30
    int res = dfs(0, 21, t);
31
    return res == INT_MAX ? -1 : res;
32
  }
33
};