LeetCode 256. 粉刷房子

2026-07-01 HGNULB 约 4 分钟

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

分类

题目描述

✅ 256. 粉刷房子

题意分析

一排房子要逐间刷漆，costs[i][j] 是把第 i 间房子刷成第 j 种颜色的花费，一共只有三种颜色。唯一的限制是相邻两间房子颜色不能相同，要求刷完所有房子的最小总花费。

约束信号很明确：限制只发生在「相邻」两间之间，不跨越更远的距离。这意味着做第 i 间房子的决策时，需要知道的历史信息只有第 i - 1 间房子刷了什么颜色，再往前的选择不影响当前是否合法。颜色只有 3 种，是一个常数，可以直接把颜色枚举进状态里。

边界方面：房子数量可能为 0，此时花费是 0；只有一间房子时不存在相邻约束，答案就是这一行三个花费的最小值；花费都是非负数，不必担心负权带来的反直觉最优解。

解法：滚动 DP

核心思路

相邻约束只与上一间房子的颜色有关，无须保存完整刷色方案。处理完第 i 间房子后，令 r、g、b 分别表示第 i 间刷成红、绿、蓝时的最小总花费。

以红色为例，第 i 间刷红时，上一间只能是绿或蓝，因此：
\[nextR = costs[i][0] + \min(g, b)\]
绿色和蓝色同理。循环不变量是：每轮开始时，r、g、b 完整表示上一间房子的三个最优状态。每个新状态枚举了所有合法前驱，并选择其中花费最小者，因此不会漏掉更优方案；一轮算完后不变量对下一间房子继续成立。

三个新状态都依赖旧状态，必须先算进 nextR、nextG、nextB，再统一覆盖。若边算边覆盖，后续转移会混用本轮新值，状态含义就被破坏。由于只依赖上一层，三个滚动状态已经足够。

解题步骤

空数组直接返回 0；否则用第一间房子的三种花费初始化 r、g、b。

从第二间房子开始，分别从另外两种颜色的旧状态转移，得到三个 next 状态。

三个新状态全部算完后统一覆盖旧状态。

最后一间房子的颜色不限，返回 r、g、b 的最小值。

例如 costs = [[17,2,17],[16,16,5],[14,3,19]]：初始状态为 [17,2,17]，处理后两间房子依次得到 [18,33,7]、[21,10,37]，答案是 10，对应绿、蓝、绿。

代码实现

class Solution {
    public int minCost(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }

        int r = costs[0][0], g = costs[0][1], 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)$。只保存上一层和当前层的三个状态。

关键点总结

状态必须保留上一间房子的颜色，才能在转移时表达「相邻不同色」。

nextColor 只能从另外两种颜色转移；这既保证合法，也覆盖全部合法前驱。

滚动优化不改变转移，只减少存储；覆盖前必须先算完整个新状态。

若颜色扩展到 k 种，可维护上一层最小值和次小值，避免对每种颜色重复扫描其余 k - 1 种颜色。

易错点总结

原地依次更新三个旧状态：后算的颜色会读到本轮新值。必须用三个临时变量保存新层。

允许从相同颜色转移：[[1,100,100],[1,100,100]] 会错误得到 2；相邻不同色的正确答案是 101。

循环从第 0 间开始：第一间房子的花费会被重复计算；初始化后应从下标 1 开始。

固定返回某一种颜色：最后一间没有指定颜色，必须在三个收尾状态中取最小值。

相似题目

题目	难度	考察点
265. 粉刷房子 II	困难	颜色数扩展到 k，需维护最小与次小把转移压回 $O(k)$
1473. 粉刷房子 III	困难	多出「恰好分成 target 个街区」的第三维状态
LCR 091. 粉刷房子	中等	完全同题换号，适合做隔日默写复盘