LeetCode LCR 091. 粉刷房子

约 4 分钟
文章信息 5 个分类 3 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 动态规划 LCR

题目描述

✅ LCR 091. 粉刷房子

image-20260929004151520

image-20260929004151521

题意分析

每间房都要刷成红、蓝、绿三种颜色之一，相邻两间不能同色，costs[i][j] 表示第 i 间刷成第 j 种颜色的花费。要求所有房子的最小总花费，不需要输出具体配色。

当前能用什么颜色，只取决于上一间的颜色。因此不能只保存前缀的一个最小费用，而要分别记录上一间刷成三种颜色时的最小费用；更早的具体配色不必保留。

解法：三色状态滚动递推

核心思路

[!blue]

代码中的 r、g、b 分别对应颜色下标 0、1、2，也就是题面中的红、蓝、绿。每处理完一间房，它们表示刷完当前前缀、最后一间固定为对应颜色的最小总花费。

当前房子刷成某种颜色时，上一间只能从另外两种颜色中选择。例如刷成下标 0 的颜色，最优费用就是 min(旧 g, 旧 b) + cost[0]。另外两种颜色同理，既排除了相邻同色，也枚举了全部合法的前驱颜色。

同一种末尾颜色下，费用更高的历史方案不会带来更多后续选择，所以只保留最小费用不会丢失最优解。由此得到三条转移：

  • r = min(_g, _b) + cost[0]
  • g = min(_r, _b) + cost[1]
  • b = min(_r, _g) + cost[2]

_r、_g、_b 必须都是上一轮的值。先整体保存旧状态，再计算新状态，才能保证每次只加入一间房；直接顺序读取更新后的变量会混用两层费用，重复计入当前房子的成本。

初始三个费用都为零，用空前缀统一处理第一间房。全部刷完后，末尾颜色没有限制，取三个状态的最小值。

解题步骤

  1. 初始化 r = g = b = 0。
  2. 依次读取每间房的三种费用，先把上一轮状态保存到 _r、_g、_b。
  3. 对每种当前颜色，取另外两种旧状态中的较小值，再加当前颜色的费用。
  4. 返回三个最终状态的最小值。只有一间房时，第一轮直接得到它的三种费用，因此也自然返回该行最小值。

代码实现

class Solution {
    public int minCost(int[][] costs) {
        // r / g / b：最后一间分别刷成红 / 蓝 / 绿时的最小总花费。
        // 初值 0 表示「尚未刷任何房子」，让第一间无需特判。
        int r = 0;
        int g = 0;
        int b = 0;

        for (int[] cost : costs) {
            // 三条转移互相引用，必须先快照旧值。
            int _r = r;
            int _g = g;
            int _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)$，每间房只计算固定的三种颜色状态。
  • 空间复杂度：$O(1)$，只保存三个旧状态与三个新状态。

关键点总结

[!green]

  • 状态要记录末尾颜色，因为它决定下一间的可选颜色。
  • 每个新状态只从另外两种旧颜色转移，直接保证相邻不同色。
  • 三条转移属于同一轮，必须统一读取上一轮的快照。
  • 最后一间可以是任意颜色，答案要在三个最终状态中取最小值。

易错点总结

[!yellow]

  • 当前房子某种颜色只能接上一房子的另外两种颜色，不能把同色状态加入转移。
  • 三个新状态都依赖上一轮，先保存旧值或使用同时赋值，不能顺序读到新值。
  • 最后取三种末尾颜色的最小值，不固定某一种颜色。

相似题目

题目 难度 关联与区别
265. 粉刷房子 II 困难 把三种颜色扩展为k种，可维护前一行最小与次小值，避免逐颜色枚举所有其他颜色。
64. 最小路径和 中等 同样在分层状态中累计最小费用，本题禁止相邻房子同色，原题由网格移动限制前驱。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/19211492
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！