LeetCode 1473. 粉刷房子 III
题目描述
题意分析
有一排
m间房子，可以使用编号一到n的颜色。houses[i] == 0表示尚未粉刷，需要选择颜色并支付对应费用；非零表示颜色已经确定，不能重新粉刷，也不再产生费用。一个街区是连续且颜色相同的最大一段房子。同一种颜色如果被其他颜色隔开，会属于不同街区，所以街区数不是使用过的颜色种类数。
要求给所有未刷房子定色，使整排恰好形成
target个街区，并让新增粉刷费用最低。不能只要求街区数不超过目标；如果固定颜色与可选颜色无法满足要求，返回-1。
解法：三维动态规划记录位置、颜色和街区数
核心思路
[!blue]
从左到右粉刷时，下一间是否增加街区，只取决于它的颜色与前一间颜色是否相同。因此状态必须同时记住已处理位置、末尾颜色和已有街区数。定义
dp[i][color][blocks]为前i间房子全部确定后，最后颜色为color、恰好形成blocks个街区的最小费用。对于当前颜色
color，枚举上一间颜色preColor。如果两色相同，当前房子延续已有街区，前一状态也需要blocks个街区；如果不同，就新开一个街区，前一状态应只有blocks - 1个。对每个可达来源，加上当前需要支付的费用，取最小值。相同位置、末色和街区数的不同粉刷历史，后续允许的选择完全相同，只有累计费用有差别，因此只保留最便宜的历史不会损失全局最优解。这也说明不能省略末色：只知道街区数，无法判断下一间会延续还是新开街区。
已涂色房子只能枚举其指定颜色，新增费用为零；未涂色房子才允许全部实际颜色，并支付
cost[i - 1][color - 1]。已有颜色仍然参与相邻比较，不能直接跳过，否则街区边界会出错。用虚拟颜色零表示尚未处理任何房子的空前缀，仅初始化
dp[0][0][0] = 0，其余状态全为不可达。第一间房子的实际颜色必定不同于零，会自然新增第一个街区。虚拟颜色不会赋给真实房子，也不会在后续层产生可达状态。全部房子处理完后，只考虑恰好
target个街区，在所有可能的末尾颜色中取最低费用。所有候选仍不可达时返回-1；不可达状态不能拿来正常累加转移。
解题步骤
- 创建三维状态表并初始化为正无穷哨兵，只有空前缀、虚拟颜色零、零街区的费用为零。
- 依次处理每间房子，枚举当前实际颜色，跳过与已有颜色冲突的选择。
- 确定当前费用：已刷房子为零，未刷房子查对应的费用表。
- 枚举上一颜色与当前街区数；同色使用同样的前一街区数，异色使用少一个的前一街区数。
- 从可达前一状态转移，加上当前费用并更新最小值。
- 在最后一层所有末色的
target状态中取最小值，无可达方案则返回-1。
代码实现
class Solution {
public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
int inf = 1_000_000_000;
// dp[i][c][b]：前 i 栋刷完、末栋颜色 c、共 b 个街区的最小花费。
int[][][] dp = new int[m + 1][n + 1][target + 1];
for (int i = 0; i <= m; i++) {
for (int color = 0; color <= n; color++) {
Arrays.fill(dp[i][color], inf);
}
}
// 颜色 0 是不存在的哨兵，让第一栋房子自动走「变色加街区」分支。
dp[0][0][0] = 0;
for (int i = 1; i <= m; i++) {
for (int color = 1; color <= n; color++) {
// 已刷过的房子颜色被锁死，不能枚举成别的颜色。
if (houses[i - 1] != 0 && houses[i - 1] != color) {
continue;
}
// 已刷过的房子不产生任何花费。
int paintCost = 0;
if (houses[i - 1] == 0) {
paintCost = cost[i - 1][color - 1];
}
// preColor 从 0 开始，必须包含哨兵颜色。
for (int preColor = 0; preColor <= n; preColor++) {
for (int blocks = 1; blocks <= target; blocks++) {
int preBlocks = blocks;
if (color != preColor) {
preBlocks = blocks - 1;
}
if (preBlocks < 0 || dp[i - 1][preColor][preBlocks] == inf) {
continue;
}
dp[i][color][blocks] =
Math.min(
dp[i][color][blocks],
dp[i - 1][preColor][preBlocks] + paintCost);
}
}
}
}
int answer = inf;
for (int color = 1; color <= n; color++) {
answer = Math.min(answer, dp[m][color][target]);
}
if (answer == inf) {
return -1;
}
return answer;
}
}
func minCost(houses []int, cost [][]int, m int, n int, target int) int {
const inf = 1000000000
// dp[i][c][b]：前 i 栋刷完、末栋颜色 c、共 b 个街区的最小花费。
dp := make([][][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([][]int, n+1)
for color := 0; color <= n; color++ {
dp[i][color] = make([]int, target+1)
for blocks := 0; blocks <= target; blocks++ {
dp[i][color][blocks] = inf
}
}
}
// 颜色 0 是不存在的哨兵，让第一栋房子自动走「变色加街区」分支。
dp[0][0][0] = 0
for i := 1; i <= m; i++ {
for color := 1; color <= n; color++ {
// 已刷过的房子颜色被锁死，不能枚举成别的颜色。
if houses[i-1] != 0 && houses[i-1] != color {
continue
}
// 已刷过的房子不产生任何花费。
paintCost := 0
if houses[i-1] == 0 {
paintCost = cost[i-1][color-1]
}
// preColor 从 0 开始，必须包含哨兵颜色。
for preColor := 0; preColor <= n; preColor++ {
for blocks := 1; blocks <= target; blocks++ {
preBlocks := blocks
if color != preColor {
preBlocks = blocks - 1
}
if preBlocks < 0 || dp[i-1][preColor][preBlocks] == inf {
continue
}
cand := dp[i-1][preColor][preBlocks] + paintCost
if cand < dp[i][color][blocks] {
dp[i][color][blocks] = cand
}
}
}
}
}
answer := inf
for color := 1; color <= n; color++ {
if dp[m][color][target] < answer {
answer = dp[m][color][target]
}
}
if answer == inf {
return -1
}
return answer
}
复杂度分析
- 时间复杂度：
O(m × target × n²)。每个位置、末色和街区数构成一个状态，转移枚举至多n + 1个前一颜色。- 空间复杂度：
O(m × target × n)，当前实现保存完整三维状态表。
关键点总结
[!green]
- 街区由连续同色段决定，相同颜色可以在不同位置形成多个街区。
- 末尾颜色决定是否新开街区，位置、末色和街区数一起构成足够的状态。
- 固定颜色限制选择但仍参与街区划分，只有未刷房子产生费用。
- 唯一的空前缀哨兵让第一间房子的首街区自然产生。
- 最终固定街区数量，再跨全部末尾颜色取最小值。
易错点总结
[!yellow]
- 把街区数当颜色种数：被其他颜色隔开的相同颜色不属于同一个连续街区。
- 给已涂色房子换色或再次收费：它们只能保留原颜色，新增费用为零。
- 跳过已刷房子不更新状态：固定颜色也会与前后房子形成或打断街区。
- 不记录末尾颜色：无法判断下一间是否增加街区，状态信息不足。
- 全部空前缀状态初始化为零：会凭空产生已有颜色和街区，只有
dp[0][0][0]可达。- 最终对不超过目标的街区数取最小值：题目要求恰好目标数量，不能混入更少街区。
- 只查看某一种末尾颜色：最优方案可能以任意合法颜色结束。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 256. 粉刷房子 | 中等 | 本题允许相邻同色并精确限制街区数，还包含已涂色房屋，不能只沿用相邻必须不同的状态。 |
| 265. 粉刷房子 II | 困难 | 颜色数推广后仍可借鉴前层颜色转移，本题还要增加已形成街区数维度。 |