本题是一个三维 DP。

f[i][j][k] 表示染完前 i 个房子时有 j 个街区（只从前 i 个房子考虑），且第 i 个房子的颜色是 k 的所有方案。存储的值是代价最小值。

按第 i-1 个房子的颜色划分集合。

当第 i-1 个房子的颜色是 u 时：

如果 u = k，那么第 i-1 个房子和第 i 个房子是一个街区，f[i][j][k] = f[i-1][j][u] + cost[i][k]，u 取 1, 2, 3, …, n。

如果 u ≠ k，那么第 i-1 个房子和第 i 个房子是不同的街区，f[i][j][k] = f[i-1][j-1][u] + cost[i][k]，u 取 1, 2, 3, …, n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
 public:
  int minCost(vector<int>& hs, vector<vector<int>>& cost, int m, int n, int target) {
    const int INF = 1e8;
    vector<vector<vector<int>>> f(m, vector<vector<int>>(m + 1, vector<int>(n + 1, INF)));
    if (hs[0]) // 初始化时，如果第 0 间房子已经染色了，那么不用再染，代价为 0
      f[0][1][hs[0]] = 0;
    else { // 初始化时，如果第 0 间房子没有染色，就枚举每种可以染的的颜色，初始化相应状态为代价值
      for (int i = 1; i <= n; i++) {
        f[0][1][i] = cost[0][i - 1];
      }
    }
    for (int i = 1; i < m; i++) {
      for (int j = 1; j <= target; j++) {
        if (hs[i]) {
          int k = hs[i];
          for (int u = 1; u <= n; u++) {
            if (u == k)
              f[i][j][k] = min(f[i][j][k], f[i - 1][j][u]);
            else
              f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][u]);
          }
        } else {
          // 枚举当前房子 i 染成的颜色
          for (int k = 1; k <= n; k++) {
            // 枚举前一间房子 i-1 染成的颜色
            for (int u = 1; u <= n; u++) {
              if (u == k)
                f[i][j][k] = min(f[i][j][k], f[i - 1][j][u] + cost[i][k - 1]);
              else
                f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][u] + cost[i][k - 1]);
            }
          }
        }
      }
    }
    int res = INF;
    for (int i = 1; i <= n; i++) res = min(res, f[m - 1][target][i]);
    if (res == INF) res = -1;
    return res;
  }
};