LeetCode 256. 粉刷房子
题目描述
题意分析
每间房子有三种颜色可选，
costs[i]的三列给出第i间房子涂成各颜色的费用。所有房子都要粉刷，相邻房子的颜色必须不同，求最小总费用。
解法：滚动 DP
核心思路
[!blue]
当前房子能用哪些颜色，只取决于上一间房子的颜色。因此处理完一段前缀后，不必保留每一种粉刷方案，只需按最后一间的三种颜色，分别保留累计费用最小的方案。相同末尾颜色的其他更贵方案，对后面的限制完全一样，永远不会更优。
用
r、g、b表示这三个最小累计费用，分别对应costs的第 0、1、2 列。它们不是上一间单独的粉刷费用，而是从第一间到上一间全部粉刷完成的总费用。若当前房子选择第 0 列的颜色，上一间只能选择另外两种颜色，所以
nextR = costs[i][0] + min(g, b)。同理，nextG = costs[i][1] + min(r, b)，nextB = costs[i][2] + min(r, g)。这既排除了相邻同色，也枚举了每种当前颜色的全部合法前驱，因此取最小值就得到当前前缀的最优费用。每一层只依赖上一层的三个数，可以滚动保存。但三个新值都必须读取旧状态，所以要先算出
nextR、nextG、nextB，再统一覆盖r、g、b。第一间房子没有相邻约束，三个状态直接初始化为它的三种费用。处理完最后一间后，没有规定它必须是什么颜色，因此返回三个状态中的最小值。
解题步骤
- 代码对空数组返回
0；非空时，用第一间房子的三种费用初始化r、g、b。- 从第二间房子开始，分别从另外两种颜色的旧状态转移，得到三个
next状态。- 三个新状态全部算完后统一覆盖旧状态。
- 最后一间房子的颜色不限，返回
r、g、b的最小值。只有一间房子时，循环不会执行，直接从它的三种费用中取最小值即可。
代码实现
class Solution {
public int minCost(int[][] costs) {
if (costs == null || costs.length == 0) {
return 0;
}
// 三个状态都是截至当前房子、以对应颜色结束的累计最小费用。
int r = costs[0][0];
int g = costs[0][1];
int b = costs[0][2];
for (int i = 1; i < costs.length; i++) {
// 全部新颜色只读取上一间状态，三个新值算完后才能一起覆盖旧值。
int nextR = costs[i][0] + Math.min(g, b);
int nextG = costs[i][1] + Math.min(r, b);
int nextB = costs[i][2] + Math.min(r, g);
r = nextR;
g = nextG;
b = nextB;
}
return Math.min(r, Math.min(g, b));
}
}
func minCost(costs [][]int) int {
if len(costs) == 0 {
return 0
}
// 三个状态都是截至当前房子、以对应颜色结束的累计最小费用。
r, g, b := costs[0][0], costs[0][1], costs[0][2]
for i := 1; i < len(costs); i++ {
// 全部新颜色只读取上一间状态，三个新值算完后才能一起覆盖旧值。
nextR := costs[i][0] + min(g, b)
nextG := costs[i][1] + min(r, b)
nextB := costs[i][2] + min(r, g)
r, g, b = nextR, nextG, nextB
}
return min(r, min(g, b))
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
复杂度分析
- 时间复杂度：$O(n)$。每间房子只计算三次状态转移。
- 空间复杂度：$O(1)$。只保存上一层和当前层的三个状态。
关键点总结
[!green]
- 最后颜色相同的方案，对未来的约束相同，只需保留其中累计费用最小的一个。
- 新颜色只能从另外两种旧颜色转移，不能只保存一个不区分颜色的最小费用。
- 每层只依赖上一层，因此三个状态就能完成动态规划。
易错点总结
[!yellow]
- 原地依次更新三个旧状态：后算的颜色会读到本轮新值。必须用三个临时变量保存新层。
- 允许从相同颜色转移：会把相邻同色的非法方案计入最优值，每个新状态必须排除自己的旧颜色。
- 循环从第 0 间开始：第一间房子的花费会被重复计算；初始化后应从下标
1开始。- 固定返回某一种颜色：最后一间没有指定颜色，必须在三个收尾状态中取最小值。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 265. 粉刷房子 II | 困难 | 把三种颜色扩展为k种，可维护前一行最小与次小值，避免逐颜色枚举所有其他颜色。 |
| 64. 最小路径和 | 中等 | 同样在分层状态中累计最小费用，本题禁止相邻房子同色，原题由网格移动限制前驱。 |
| 1473. 粉刷房子 III | 困难 | 粉刷房子系列。III 允许预先着色，并要求指定街区数，需要在末尾颜色状态上增加街区计数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！