1473. 粉刷房子 III

发表于 分类于 阅读次数： Waline： 本文字数： 1.2k 阅读时长 ≈ 4 分钟

考点

  • 划分DP
  • 初始值设定

题解

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
class Solution {
 public:
  const int inf = 0x3f3f3f3f;
  int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n,
              int target) {
    // f[j][i][k]: 前i个数, 组成j个区间, 最后一个区间是第k个颜色
    // 实际上最后一个区间的颜色就是第i个数的颜色
    int f[105][105][25];
    memset(f, 0x3f, sizeof(f));
    f[0][0][0] = 0;
    for (int j = 1; j <= target; ++j) {
      for (int i = 1; i <= m; ++i) {
        for (int k = 1; k <= n; ++k) {
          if (houses[i - 1] != 0 && houses[i - 1] != k) continue;
          int c = houses[i - 1] == k ? 0 : cost[i - 1][k - 1];
          if (f[j][i - 1][k] != inf)
            f[j][i][k] = min(f[j][i][k], f[j][i - 1][k] + c);
          for (int q = 0; q <= n; ++q) {
            if (q == k) continue;
            if (f[j - 1][i - 1][q] != inf)
              f[j][i][k] = min(f[j][i][k], f[j - 1][i - 1][q] + c);
          }
        }
      }
    }
    int res = inf;
    for (int k = 1; k <= n; ++k) res = min(res, f[target][m][k]);
    return res == inf ? -1 : res;
  }
};

思路

状态转移的推导

考虑第 \(i\) 个房子最终颜色为 \(k\) 的所有情况。我们枚举所有可能的 \(j, i, k\)。

3.1 当前房子的颜色合法性

题目给出的数组 houses 表示初始颜色：

  • houses[i-1] == 0 表示第 \(i\) 个房子尚未上色，可以任意选择颜色；
  • houses[i-1] != 0 表示第 \(i\) 个房子已经被涂成某个固定颜色。

因此，当我们尝试令第 \(i\) 个房子最终颜色为 \(k\) 时，必须满足： \[ \text{houses}[i-1] = 0 \quad \text{或者} \quad \text{houses}[i-1] = k. \] 否则，这个状态不可能：

1
if (houses[i - 1] != 0 && houses[i - 1] != k) continue;

对应的「涂色代价」为：

  • 若原来已经是颜色 \(k\)：代价为 0；
  • 若原来是 0：代价为 cost[i-1][k-1]。

在代码中统一写成：

1
int c = (houses[i - 1] == k ? 0 : cost[i - 1][k - 1]);

这里可以理解为： 第 \(i\) 个房子从「当前状态」变成颜色 \(k\) 的“额外成本”（c）。

3.2 两种转移来源

令第 \(i\) 个房子是颜色 \(k\) 后，我们看第 \(i-1\) 个房子的情况。

设第 \(i-1\) 个房子的颜色为 \(q\)。有两类情况：

  1. 同色延续：\(q = k\)

    • 第 \(i-1\) 和第 \(i\) 颜色一样，不会增加新的 neighborhood；
    • neighborhoods 个数仍为 \(j\)；
    • 来源状态是 \(f[j][i-1][k]\)；
    • 第 \(i\) 个房子需要额外加上 c 这笔花费。

    对应转移： \[ f[j][i][k] = \min \big(f[j][i][k], \; f[j][i-1][k] + c \big). \] 代码：

    1
    2
    if (f[j][i - 1][k] != inf)
      f[j][i][k] = min(f[j][i][k], f[j][i - 1][k] + c);

  2. 异色开启新区间：\(q \ne k\)

    • 第 \(i\) 的颜色与第 \(i-1\) 不同，会产生新的 neighborhood；
    • 因此第 \(i\) 位置结束时的区间数为 \(j\)，那么在第 \(i-1\) 位置时区间数应为 \(j-1\)；
    • 所有可能的前一色 \(q \in \{0,1,\dots,n\}\) 且 \(q \ne k\)；
      • 这里 \(q=0\) 对应「前面没有房子 / 没有颜色」，可以视作从“空状态”开出第一个 neighborhood。

    对应转移： \[ f[j][i][k] = \min\Big( f[j][i][k], \; \min_{q \ne k} \big( f[j-1][i-1][q] + c \big) \Big). \] 代码：

    1
    2
    3
    4
    5
    for (int q = 0; q <= n; ++q) {
      if (q == k) continue;
      if (f[j - 1][i - 1][q] != inf)
        f[j][i][k] = min(f[j][i][k], f[j - 1][i - 1][q] + c);
    }

综合起来，第 \(i\) 个房子颜色为 \(k\)、区间数为 \(j\) 的状态转移为： \[ f[j][i][k] = \min \left\{ \begin{aligned} &f[j][i-1][k] + c, \\ &\min_{q \ne k} \big( f[j-1][i-1][q] + c \big) \end{aligned} \right. \] 前提是该颜色选择合法，即： \[ \text{houses}[i-1] \in \{0, k\}. \]

4. 初始值设计的关键

4.1 为什么需要 \(k = 0\) 这层哨兵

最终的初始化是：

1
2
memset(f, 0x3f, sizeof(f));  // 全部 INF
f[0][0][0] = 0;

含义是：

  • \(f[0][0][0] = 0\)： 表示「前 0 个房子，0 个 neighborhoods，颜色为 0（无颜色）」的总代价为 0；
  • 其他所有 \(f[j][i][k]\) 初始为 INF，表示尚不可达。

k = 0 作为一个「虚拟颜色」，只在起点状态出现，用来优雅地处理“第一个房子开出第一个区间”的逻辑。

在转移时，异色开新区间有一条： \[ f[j][i][k] = \min_{q \ne k} \big( f[j-1][i-1][q] + c \big) \] 如果我们允许 \(q = 0\)，那么在 \(i = 1, j = 1\) 时：

  • 前一格是 “0 个房子、0 个区间、颜色 0”；
  • 第一个房子选颜色 \(k\)；
  • 这就是从空白状态开启第一个区间；
  • 代价正好就是第一个房子的上色成本 c。

形式上就是： \[ f[1][1][k] = \min_{q \ne k} \big( f[0][0][q] + c \big) \] 由于只有 \(q = 0\) 时 \(f[0][0][q]\) 不是 INF，而 \(0 \ne k\)，于是： \[ f[1][1][k] = f[0][0][0] + c = 0 + c = c. \] 这样就把「第一个房子」的 base case 自然地融合进「异色开新区间」的统一转移里了，而不用特判。