LeetCode 1473. 粉刷房子 III

2023-05-03 HGNULB 约 13 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 1473. 粉刷房子 III

题意分析

一排 m 栋房子，houses[i] 是第 i 栋的颜色（0 表示还没刷），颜色编号从 1 到 n。cost[i][j] 是把第 i 栋刷成颜色 j+1 的花费。要求把所有未刷的房子刷上颜色，使得整排房子恰好形成 target 个「街区」，并让总花费最小；做不到就返回 -1。

「街区」的定义必须先钉死：最大的连续同色房子段。[1,1,2,2,1] 的街区是 [1,1]、[2,2]、[1]，共 3 个。等价的、更适合写代码的说法是：街区数 = 1 + 相邻两栋颜色不同的次数。这个改写把一个「全局分段」的属性变成了一个可以逐位累加的量，是本题能做 DP 的根本原因。

三条约束决定了状态设计。第一，已刷过的房子不能重刷（houses[i] != 0 时颜色被锁死，花费为 0），所以枚举颜色时要过滤。第二，街区数是恰好 target，不是至多也不是至少，所以「凑不出」必须是一个可表达的状态。第三，判断相邻是否同色需要知道上一栋的颜色，因此颜色必须进状态。

规模上 m <= 100、n <= 20、target <= m <= 100。$m \cdot n \cdot target = 2 \times 10^5$ 个状态，每个状态再枚举 n 种上一颜色，总计约 $4 \times 10^6$ 次运算，$O(m \cdot n^2 \cdot target)$ 完全跑得动。这个范围本身就在提示「三维状态 + 一层决策枚举」。

边界：target > m 必然无解（每栋房子最多贡献一个街区）；所有房子都已刷好时不需要任何花费，只需检查它天然形成的街区数是否等于 target；target = 1 要求全排同色。花费上界是 $100 \times 10^4 = 10^6$，int 足够，但哨兵「无穷大」要挑得比它大且加法不溢出。

解法：三维动态规划记录位置、颜色和街区数

核心思路

暴力是枚举每栋未刷房子的颜色，$O(n^m)$，显然不行。要转 DP，得先回答一个问题：处理到第 i 栋时，后面的决策依赖前面的哪些信息？

后面要算的是「新增花费」和「街区数是否达标」。新增花费只跟当前刷什么颜色有关；而街区数是否增加，只取决于当前颜色与上一栋颜色是否相同。至于更早的房子怎么刷、街区在哪里断开，一概不影响后续——它们的全部影响已经被压缩进「已形成多少个街区」这一个数字里。

于是状态定死为三维：dp[i][c][b] 表示前 i 栋房子已全部确定颜色、第 i 栋的颜色是 c、这 i 栋房子共形成 b 个街区时的最小总花费；无法达成则为无穷大。这里 i 从 1 到 m（表示「前 i 栋」），c 从 1 到 n，b 从 1 到 target。

转移是枚举上一栋的颜色 pc：

若 c == pc，两栋同色不产生新街区，来源是 dp[i-1][pc][b]；

若 c != pc，颜色变了，街区数加一，来源是 dp[i-1][pc][b-1]。

两种情况都再加上把第 i 栋刷成 c 的花费 paintCost：已刷房子为 0，未刷房子为 cost[i-1][c-1]。

初始状态用一个虚拟的「第 0 栋」：dp[0][0][0] = 0，其中颜色 0 是一个不存在的哨兵颜色，街区数为 0。它的妙处在于——第 1 栋房子无论刷什么颜色 c，都满足 c != 0，于是自动走「街区数加一」的分支，得到 dp[1][c][1]。这正是我们想要的语义：第一栋房子必然独自开启第一个街区。用一个不可能与真实颜色相等的哨兵，把「首栋房子」的特判并入通用转移，是这道题最优雅的一笔。

不变量：填完 dp[i][c][b] 后，它精确等于「前 i 栋房子合法着色、末栋为 c、街区数为 b」的最小花费；若这种组合不可能出现（例如 b > i，或第 i 栋已被刷成别的颜色），则它保持无穷大。答案是 min over c of dp[m][c][target]，全为无穷大就返回 -1。

解题步骤

开三维表并全填无穷大，只把 dp[0][0][0] 置 0。无穷大取 $10^9$：它严格大于最大可能花费 $10^6$，加上单次花费也不会溢出。无论哨兵取什么值，转移前都必须跳过不可达来源，不能拿哨兵参与加法。

外层枚举房子 i 从 1 到 m：依赖 dp[i-1][*][*]，行序递增天然满足。

枚举当前颜色 c 从 1 到 n，先过滤非法：houses[i-1] != 0 && houses[i-1] != c 时直接 continue——这栋房子已经刷成别的颜色了，不可能是 c。这一行是「已刷不能重刷」的全部实现。

算 paintCost：houses[i-1] == 0 时取 cost[i-1][c-1]，否则为 0。已刷的房子不产生任何花费，这一点漏了会把答案算大。

枚举上一颜色 pc 从 0 到 n：注意下界是 0 而不是 1，必须把哨兵颜色包含进来，否则第 1 栋房子找不到任何来源，整张表全是无穷大。

枚举街区数 b 从 1 到 target：b 从 1 起步是因为任何非空前缀至少有一个街区。据 c 与 pc 是否相等决定来源的街区维度是 b 还是 b-1。

过滤不可达来源：preBlocks < 0 或 dp[i-1][pc][preBlocks] 为无穷大时跳过。前者防越界，后者避免用「不可能的前缀」推出「看似可行」的后继。

统计答案：对所有颜色取 dp[m][c][target] 的最小值，仍是无穷大则返回 -1。注意返回 -1 而不是无穷大本身。

以 houses = [0, 0, 0, 0, 0]、cost = [[1,10],[10,1],[10,1],[1,10],[5,1]]、m = 5、n = 2、target = 3 走一遍。也就是每栋房子刷颜色 1 或颜色 2 的花费分别是 (1,10)、(10,1)、(10,1)、(1,10)、(5,1)。

i = 1：来源只有 dp[0][0][0] = 0。c = 1 时 c != 0 走加街区分支，dp[1][1][1] = 0 + 1 = 1；c = 2 同理 dp[1][2][1] = 10。

i = 2（花费 c=1 花 10、c=2 花 1）：
dp[2][1][1]：来自 dp[1][1][1] = 1（同色不加街区），得 1 + 10 = 11。
dp[2][1][2]：来自 dp[1][2][1] = 10（变色加街区），得 10 + 10 = 20。
dp[2][2][1]：来自 dp[1][2][1] = 10，得 10 + 1 = 11。
dp[2][2][2]：来自 dp[1][1][1] = 1，得 1 + 1 = 2。

i = 3（c=1 花 10、c=2 花 1）：
dp[3][1][1]：只能同色来自 dp[2][1][1] = 11 → 21。
dp[3][2][1]：只能同色来自 dp[2][2][1] = 11 → 12。
dp[3][1][2]：同色来自 dp[2][1][2] = 20 → 30；变色来自 dp[2][2][1] = 11 → 21。取 21。
dp[3][2][2]：同色来自 dp[2][2][2] = 2 → 3；变色来自 dp[2][1][1] = 11 → 12。取 3。
dp[3][1][3]：变色来自 dp[2][2][2] = 2 → 12；同色来自 dp[2][1][3]（无穷大）。取 12。
dp[3][2][3]：变色来自 dp[2][1][2] = 20 → 21；同色来自 dp[2][2][3]（无穷大）。取 21。

i = 4（c=1 花 1、c=2 花 10）：
dp[4][1][2]：同色来自 dp[3][1][2] = 21 → 22；变色来自 dp[3][2][1] = 12 → 13。取 13。
dp[4][1][3]：同色来自 dp[3][1][3] = 12 → 13；变色来自 dp[3][2][2] = 3 → 4。取 4。
dp[4][2][2]：同色来自 dp[3][2][2] = 3 → 13；变色来自 dp[3][1][1] = 21 → 31。取 13。
dp[4][2][3]：同色来自 dp[3][2][3] = 21 → 31；变色来自 dp[3][1][2] = 21 → 31。取 31。

i = 5（c=1 花 5、c=2 花 1）：
dp[5][1][3]：同色来自 dp[4][1][3] = 4 → 9；变色来自 dp[4][2][2] = 13 → 18。取 9。
dp[5][2][3]：同色来自 dp[4][2][3] = 31 → 32；变色来自 dp[4][1][2] = 13 → 14。取 14。

答案是 min(dp[5][1][3], dp[5][2][3]) = min(9, 14) = 9，与期望一致。对应的着色是 [1, 2, 2, 1, 1]，街区为 [1]、[2,2]、[1,1] 共 3 个，花费 1 + 1 + 1 + 1 + 5 = 9。

顺带验证哨兵的作用：i = 1 时若把 pc 的下界写成 1，dp[0][pc][*] 全是无穷大，dp[1][*][*] 也就全是无穷大，整张表塌掉，最终返回 -1。

代码实现

import java.util.Arrays;

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 \cdot n^2 \cdot target)$。共有 $m \cdot n \cdot target$ 个有效状态维度，每次转移枚举至多 $n+1$ 种上一颜色；代入上限约为 $100 \times 20^2 \times 100 = 4 \times 10^6$ 次核心比较。

空间复杂度：$O(m \cdot n \cdot target)$，三维表保存每个前缀、末尾颜色和街区数的最优值。

关键点总结

把「街区数」改写成「相邻不同色的次数 + 1」，是把全局属性局部化的关键一步。任何看似「需要看完整序列才能判定」的指标，先想想能不能写成逐位可累加的形式，这是能否上 DP 的分水岭。

状态里必须带上「末栋颜色」，因为下一步的街区判定只依赖它。识别「后续决策依赖前缀的哪些信息」，是设计 DP 状态的通用方法论——依赖什么，就把什么放进状态。

哨兵颜色 0 消灭了首栋房子的特判。它与任何真实颜色都不相等，自动触发「新开街区」，让第 1 栋和第 i 栋走同一套转移代码。这个技巧比写 if (i == 1) 优雅得多，也更不容易漏边界。

恰好 target 个街区 ⇒ 不可达状态必须与高花费状态区分。用安全的有限哨兵并在转移前过滤来源，才能保证无解不会参与取最小值。

已刷房子的两处处理要成对出现：既要在枚举颜色时 continue 掉不匹配的，也要把它的 paintCost 置 0。只做一半是最常见的错法。

易错点总结

preColor 从 1 开始枚举：第 1 栋房子找不到来源，dp[1][*][*] 全是无穷大，整张表塌掉，houses = [0,0,0,0,0] 的样例返回 -1 而正确答案是 9。

不判断来源是否可达就加花费：若哨兵取 Integer.MAX_VALUE，加法会溢出为负数；即使用 $10^9$，也可能把无解状态误当成一个极昂贵但可达的方案。

忘记过滤已刷房子：houses = [0,2,1,2,0] 中第 2 栋已经是颜色 2，若仍枚举它刷成颜色 1，会算出一个物理上不可能的更低花费，样例答案 11 会被算成更小的值。

已刷房子仍累加 cost：同一用例里给第 2 栋加上 cost[1][1] 的花费，答案整体偏大。已刷的花费必须是 0。

街区维度从 0 开始枚举 blocks：blocks = 0 时若 c != pc 会取到 preBlocks = -1，数组下标为负直接越界；即使加了 preBlocks < 0 的判断，blocks = 0 也是无意义的状态（非空前缀至少 1 个街区）。

同色/异色的街区增减写反：写成同色时 preBlocks = blocks - 1，houses = [0,0,0,0,0]、target = 3 会得到完全错误的分段计数，输出偏离期望值。

答案对所有街区数取最小：题目要求恰好 target，若把 b != target 的状态也纳入，样例可能选到街区更少但更便宜的非法方案。

无解时返回无穷大或 0：houses = [1,1,1]、target = 2 时颜色已锁定且只能形成 1 个街区，必须返回 -1。

相似题目

题目	难度	考察点
256. 粉刷房子	中等	固定 3 色且不限制街区数，状态只有「位置 + 末栋颜色」两维
265. 粉刷房子 II	困难	颜色数变为 `k`，核心是用最小值/次小值把 $O(nk^2)$ 优化到 $O(nk)$
LCR 091. 粉刷房子	中等	与 256 同题，适合用来先把「末栋颜色进状态」这一维练熟
813. 最大平均值和的分组	中等	同样带「恰好分成 k 段」的维度，但段内收益是平均值而非逐位花费
410. 分割数组的最大值	困难	也是「恰好 k 段」，目标改为最小化段和的最大值，还可用二分答案替代 DP
309. 买卖股票的最佳时机含冷冻期	中等	同为「把影响后续决策的信息压进状态」的状态机 DP，维度是持仓与冷冻标记