LeetCode LCR 091. 粉刷房子
目录
题目描述
题意分析
一排房子，每间必须刷成红、蓝、绿三色之一，相邻两间不能同色。
costs[i][j]给出把第i间刷成第j种颜色的花费。求刷完所有房子的最小总花费。
与打家劫舍同属「一维序列上逐位决策」的题型，但决策的形态变了：打家劫舍每位是二值的「选或不选」，本题每位有三种取值，且约束是「当前取值不能等于前一位的取值」。这意味着只记一个「前缀最优值」不够了——必须知道前一间刷的是哪种颜色，才能判断当前间哪些颜色可用。这是本题状态需要多一个维度的根本原因。
反过来说，需要携带的信息也就仅此而已：再往前的房子刷了什么颜色，对当前决策毫无影响。约束只跨越一格，无后效性成立，可以逐间递推。
题目只要最小总花费，不要具体配色方案，所以不必枚举 $3^n$ 种涂法。约束里
costs的行数最多 100、每个花费不超过 20，规模极小，考的仍然是状态设计的准确性。
边界：只有一间房时答案是该行三个数的最小值；
costs至少有一行；颜色数固定为 3，所以三种颜色可以直接展开成三个变量，不必写成循环——这也让代码更贴近白板手写的场景。
解法：动态规划递推
核心思路
暴力做法是枚举每间房的颜色，共 $3^n$ 种方案，逐一检查相邻是否冲突并求和。瓶颈同样是重复子问题：「前
i间房刷完、且第i间刷成红色的最小花费」这个子问题，被前面各种不同的配色方案反复求解了很多次。
关键观察是：当我们站在第
i间房前，前面的配色细节可以全部丢弃，只需保留三个数——第i-1间刷成红、蓝、绿各自对应的最小前缀花费。因为第i间的可选颜色只受第i-1间的颜色制约，而每种颜色下我们只关心最省的那种历史走法。
于是定义三个状态变量：
r、g、b分别表示「已处理的房子全部刷完、且最后一间刷成红/蓝/绿」时的最小总花费。处理第i间房时的转移是：
r' = min(g, b) + cost[0]，g' = min(r, b) + cost[1]，b' = min(r, g) + cost[2]
每条式子的含义都一样：本间刷某色，就要付这一色的花费，而前一间必须是另外两色中更省的那个。三条式子右侧引用的全是旧值，所以必须先把
r、g、b整体快照下来再更新，否则算第二条时用到的r已经是本轮刚写入的新值，等价于允许了相邻同色。
要维持的不变量是：每处理完一间房，
r、g、b三个数分别是「以该间房为末尾、且末尾颜色为红/蓝/绿」的最优前缀花费，三者互不干扰。初值全为 0，对应「一间房都还没刷」，此时三种末尾颜色都尚未产生任何花费，语义自洽——第一间房的转移会得到r = 0 + cost[0]，正是我们想要的。
全部处理完后，最后一间可以是任意颜色，取
min(r, g, b)即为答案。
解题步骤
- 用三个标量而不是二维数组：颜色只有三种且题目写死，展开成
r、g、b既省掉了内层循环，也把「相邻不同色」直接体现在了三条式子的下标上，白板上写起来更清楚。空间也随之降到常数。
- 初值全设为 0：含义是「尚未刷任何房子」。这个初值让第一间房无需特判——转移式自然退化成
r = 0 + cost[0]，即第一间刷红的花费就是它自己的价格。
- 每轮先快照旧值：
int _r = r, _g = g, _b = b;。这是全题最关键的一行。三条转移式互相引用，若不快照，第二条里的_r就变成了本轮刚算出的红色新值，等于允许「本间刷蓝、前一间也是本间刷的红」这种自相矛盾的转移。
- 三条转移各取另外两色的较小者：
r = min(_g, _b) + cost[0]，g = min(_r, _b) + cost[1]，b = min(_r, _g) + cost[2]。每条式子里绝不能出现与自己同色的旧值，这就是「相邻不同色」的全部编码。
- 返回三者最小值：
Math.min(r, Math.min(g, b))。最后一间刷什么颜色都合法，所以三个候选都要参与比较。
以
costs = [[17, 2, 17], [16, 16, 5], [14, 3, 19]]走一遍，答案应为 10。
初始
r = g = b = 0。
处理第 0 间
[17, 2, 17]：快照_r = _g = _b = 0。r = min(0, 0) + 17 = 17，g = min(0, 0) + 2 = 2，b = min(0, 0) + 17 = 17。此时三个数就是第一间各刷一色的直接花费。
处理第 1 间
[16, 16, 5]：快照_r = 17、_g = 2、_b = 17。r = min(_g, _b) + 16 = min(2, 17) + 16 = 18（第 1 间刷红，前一间取更省的蓝色 2）；g = min(_r, _b) + 16 = min(17, 17) + 16 = 33；b = min(_r, _g) + 5 = min(17, 2) + 5 = 7（第 1 间刷绿，前一间取蓝色 2）。
处理第 2 间
[14, 3, 19]：快照_r = 18、_g = 33、_b = 7。r = min(33, 7) + 14 = 21；g = min(18, 7) + 3 = 10（第 2 间刷蓝，前一间取更省的绿色 7）；b = min(18, 33) + 19 = 37。
返回
min(21, 10, 37) = 10，对应配色「蓝(2) → 绿(5) → 蓝(3)」，相邻均不同色，总花费2 + 5 + 3 = 10，与预期一致。
若漏掉快照直接顺序更新：处理第 1 间时
r先被写成 18，接着算g = min(r, _b) + 16 = min(18, 17) + 16 = 33（这里恰好没变），但算b = min(r, g) + 5 = min(18, 33) + 5 = 23就错了——正确值是 7，因为g用的是本轮刚写入的 33 而非旧值 2。最终答案会从 10 涨到 26。
代码实现
class Solution {
public int minCost(int[][] costs) {
// r / g / b：最后一间分别刷成红 / 蓝 / 绿时的最小总花费。
// 初值 0 表示「尚未刷任何房子」，让第一间无需特判。
int r = 0, g = 0, b = 0;
for (int[] cost : costs) {
// 三条转移互相引用，必须先快照旧值。
int _r = r, _g = g, _b = b;
// 本间刷某色，前一间只能取另外两色中更省的那个。
r = Math.min(_g, _b) + cost[0];
g = Math.min(_r, _b) + cost[1];
b = Math.min(_r, _g) + cost[2];
}
// 最后一间刷什么颜色都合法。
return Math.min(r, Math.min(g, b));
}
}
func minCost(costs [][]int) int {
// r / g / b：最后一间分别刷成红 / 蓝 / 绿时的最小总花费。
// 初值 0 表示「尚未刷任何房子」，让第一间无需特判。
r, g, b := 0, 0, 0
for _, cost := range costs {
// 三条转移互相引用，必须先快照旧值。
_r, _g, _b := r, g, b
// 本间刷某色，前一间只能取另外两色中更省的那个。
r = min(_g, _b) + cost[0]
g = min(_r, _b) + cost[1]
b = min(_r, _g) + cost[2]
}
// 最后一间刷什么颜色都合法。
return min(r, min(g, b))
}
复杂度分析
- 时间复杂度：$O(n)$，其中 $n$ 是房子数量。每间房做 3 次取最小和 3 次加法，都是常数操作，与颜色数 3 无关地保持常数。
- 空间复杂度：$O(1)$，只用了
r、g、b与三个快照变量，共 6 个整数，与房子数量无关。若写成n × 3的二维数组是 $O(n)$，但由于状态只回看一行，滚动成标量是自然的选择。
关键点总结
- 当「当前决策受限于前一位的具体取值」时，状态必须把那个取值作为一个维度带上。打家劫舍是二值维度（偷/不偷），本题是三值维度（红/蓝/绿），推广到
k色就是k个状态——这正是「粉刷房子 II」的形态。- 多条转移互相引用时必须整体快照，否则后算的式子会读到本轮的新值。判断方法很简单：看右侧引用的变量在本轮是否已经被赋值过。这个坑在所有多状态滚动 DP 里都存在。
- 「不能与前一位相同」编码成「转移时排除同色的那一项」，而不是事后校验。约束写进转移式里，就不会产生非法状态。
- 初值 0 表示空前缀，可以省掉第一间的特判。凡是能用「空前缀」自然解释初值的 DP，都应优先这样设计，边界代码会显著变少。
- 答案要在所有末尾状态里取最优，不能只取某一个。凡是状态带了「末尾取值」维度的 DP，收尾时都要横扫这一维。
易错点总结
- 不快照直接顺序更新：
costs = [[17,2,17],[16,16,5],[14,3,19]]会算出 26 而不是 10，因为后两条式子读到了本轮刚写入的新值。- 转移里包含同色旧值，如
r = min(_r, _g, _b) + cost[0]：costs = [[1,10,10],[1,10,10]]会算出 2，等于相邻两间都刷红色，明显违规。- 只返回
r或某个固定颜色：costs = [[17,2,17]]返回 17 而不是 2，漏掉了其它末尾颜色。- 初值设成
costs[0]那一行且循环仍从第 0 行开始：costs = [[17,2,17]]会把第一间算两遍，返回 4 而不是 2。- 初值设成一个很大的数（如
Integer.MAX_VALUE）：第一轮min(_g, _b) + cost[0]会整数溢出成负数，答案变成负值。- Go 里写成
r, g, b = min(g,b)+cost[0], min(r,b)+cost[1], min(r,g)+cost[2]却拆成了三行：拆行后与 Java 的顺序错误同源，costs = [[17,2,17],[16,16,5],[14,3,19]]输出 26。- 误以为可以贪心地每间选当前最便宜的可用颜色：
costs = [[1,2,100],[1,100,100],[1,2,100]]时贪心第一间选红 1、第二间被迫选 100、第三间再选红 1，合计 102；而最优配色是蓝红蓝，2 + 1 + 2 = 5，差了 20 倍。- 把「相邻不同色」误读成「所有房子颜色都不同」：
costs有 4 行时会认为无解，实际上三色循环使用完全合法。- 遍历时用
costs[i][j]的下标却把i和j写反：costs = [[17,2,17],[16,16,5]]会按列取值导致数组越界，因为列数固定为 3 而行数可达 100。- 写成二维数组版却忘了给
dp[0]赋初值：dp[0][j]全为 0 时第一间房的花费被吞掉，costs = [[17,2,17]]返回 0。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 256. 粉刷房子 | 中等 | 与本题完全同题，代码可原样提交 |
| 265. 粉刷房子 II | 困难 | 颜色扩到 k 种，朴素转移退化为 $O(nk^2)$，需用最小与次小值优化到 $O(nk)$ |
| 1473. 粉刷房子 III | 困难 | 额外约束「恰好形成 target 个街区」，状态要再加一维已形成的街区数 |
| 198. 打家劫舍 | 中等 | 同为一维逐位决策，但每位只有二值选择，状态无需记录具体取值 |
| LCR 089. 打家劫舍 | 中等 | 与 198 同题，可对照体会「二值维度」与「三值维度」在代码上的差别 |
| 309. 买卖股票的最佳时机含冷冻期 | 中等 | 同为多状态滚动 DP，状态是持仓/冷冻/空仓三种，快照陷阱完全一致 |
| 931. 下降路径最小和 | 中等 | 转移同样排除正上方之外的越界项，但每行的可选位置由列下标决定 |