LeetCode 265. 粉刷房子 II

2023-05-03 HGNULB 约 11 分钟

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

分类

题目描述

✅ 265. 粉刷房子 II

题意分析

一排 n 个房子，每个房子必须刷成 k 种颜色之一，costs[i][j] 是把第 i 个房子刷成第 j 种颜色的开销，唯一的限制是相邻两个房子不能同色，要求刷完所有房子的最小总开销。

限制只作用在相邻两项之间，且决策沿着房子编号单向推进，这说明「处理到第 i 个房子时需要知道的全部历史信息」只有第 i-1 个房子刷了什么颜色，更早的选择不影响后续可行性。这种「无后效性 + 局部约束」是典型的逐位决策信号。

数据规模上 n 和 k 都可以到 100 量级，n * k * k 大约是 10^6，其实能过；但这题被标成困难、且经典追问就是「能否做到 $O(nk)$」，说明出题人真正考的是如何把转移里那层对上一行颜色的枚举去掉。

边界包括：costs 为空时答案为 0；只有一个房子时答案是该行最小值；k = 1 且 n >= 2 时无解——不过题目数据保证不会出现这种情况，实现上只要不特意去访问不存在的次小值就不会崩。

解法：DP + 最小二值

核心思路

先按定义写朴素转移。设 dp[i][j] 表示「把前 i+1 个房子全部刷完、且第 i 个房子刷成颜色 j 时的最小总开销」。转移是 dp[i][j] = costs[i][j] + min{ dp[i-1][c] : c != j }，初值 dp[0][j] = costs[0][j]，答案是 min(dp[n-1][*])。这个式子正确，但内层要对每个 j 枚举全部 c，单行代价是 $O(k^2)$，总代价 $O(nk^2)$。

瓶颈很清楚：对同一行的 k 个不同的 j，我们都在对几乎同一个集合 dp[i-1][*] 求最小值，区别仅仅是各自排除掉一个元素。这是重复劳动。

关键观察是：从一个集合里「排除某一个元素后的最小值」只有两种可能——如果被排除的不是最小值本身，答案就是最小值；如果被排除的恰好是最小值，答案就是次小值。也就是说，整行只需要知道上一行的最小值和次小值这两个数字（以及最小值所在的列），就能在 $O(1)$ 时间内回答任意一个 j 的转移需求。

由此把状态压成一维滚动数组。不变量是：每轮外层循环开始时，dp[j] 存的是「前 i 个房子已刷完且第 i-1 个房子颜色为 j」的最小总开销；min1 和 min2 分别是本轮开始时 dp 中最小值和次小值所在的下标，满足 dp[min1] <= dp[min2] <= dp[c] 对所有其余 c 成立。

有了这条不变量，新一行的转移就是 ndp[j] = costs[i][j] + (j == min1 ? dp[min2] : dp[min1])，单行两遍线性扫描即可。

这里用下标而不是数值来记录最小/次小，是为了能直接用 j == min1 判断「当前颜色是否就是上一行的最优颜色」；若只记数值，遇到多列取值相同时就分不清该不该退让。

解题步骤

先处理 costs 为空的情况直接返回 0。之所以要判，是因为后面要用 costs[0].length 取颜色数，空输入会越界。

用长度为 k 的一维数组 dp 作为滚动状态，初始全为 0。之所以初值取 0 而不是 costs[0]，是因为下面的主循环从 i = 0 开始就把 costs[0][j] 加上了，全零的 dp 恰好表示「还没刷任何房子，任何颜色的历史开销都是 0」，这样第一轮的 min1、min2 都指向值为 0 的列，转移结果正是 costs[0][j]，与朴素定义的初值一致，省掉了单独的初始化分支。

每轮外层循环先扫一遍 dp 找出最小值下标 min1 和次小值下标 min2。之所以要在计算新行之前先找，是因为整行转移共享同一份上一行信息，先算好一次就能被 k 个转移复用，这正是从 $O(k^2)$ 降到 $O(k)$ 的地方。

找最小/次小时用 -1 表示「尚未确定」。之所以不用 Integer.MAX_VALUE 作哨兵，是因为这里记的是下标不是数值，-1 是天然的非法下标，判断 min1 == -1 比比较数值更直白，也避免了开销累加后逼近 int 上界时的误判。

更新逻辑必须是「先判是否比最小还小，是则把旧最小挤成次小」，否则才去更新次小。之所以顺序不能颠倒，是因为新来的元素若小于当前最小，它同时也小于当前次小，直接改次小会丢掉真正的第二名。

第二遍循环生成新行：对每个 j，取 dp[min1] 作为基准，仅当 j == min1 且次小存在时改取 dp[min2]，再加上 costs[i][j]。之所以只在 j == min1 时退让，是因为只有这一列会撞上「相邻同色」的禁令，其余列都可以放心接在最优列后面。

用新数组整体替换 dp，进入下一轮。之所以要新开数组而不是原地改，是因为本行的每个 ndp[j] 都依赖上一行的完整信息，原地写会污染尚未读取的 dp 元素。

全部房子处理完后，答案是 dp 中的最小值。之所以要再扫一遍，是因为最后一个房子刷成哪种颜色没有约束，取全局最优即可。

以 costs = [[1, 5, 3], [2, 9, 4]] 走一遍，n = 2，k = 3。

初始 dp = [0, 0, 0]。第一轮 i = 0：扫描找极值，j = 0 时 min1 = 0；j = 1 时 dp[1] = 0 不小于 dp[0] = 0，进入 else，min2 = 1；j = 2 时既不小于 dp[min1] 也不小于 dp[min2]，不更新。得 min1 = 0、min2 = 1。生成新行：j = 0 撞上 min1，取 dp[min2] = 0，得 ndp[0] = 1 + 0 = 1；j = 1 取 dp[min1] = 0，得 5；j = 2 同理得 3。dp = [1, 5, 3]。

第二轮 i = 1：扫描 dp = [1, 5, 3]，j = 0 令 min1 = 0；j = 1 不小于 1，min2 = 1；j = 2 的 3 不小于 dp[min1] = 1，但小于 dp[min2] = 5，故 min2 = 2。得 min1 = 0（值 1）、min2 = 2（值 3）。生成新行：j = 0 撞上 min1，取 dp[min2] = 3，得 2 + 3 = 5；j = 1 取 dp[min1] = 1，得 9 + 1 = 10；j = 2 取 1，得 4 + 1 = 5。dp = [5, 10, 5]。

收尾取最小值 5。人工核对：第一间刷颜色 0 花 1、第二间刷颜色 2 花 4，合计 5，且颜色不同，确实是最优解。

代码实现

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

        int k = costs[0].length;
        int[] dp = new int[k];

        for (int i = 0; i < costs.length; i++) {
            int min1 = -1;
            int min2 = -1;

            for (int j = 0; j < k; j++) {
                if (min1 == -1 || dp[j] < dp[min1]) {
                    min2 = min1;
                    min1 = j;
                } else if (min2 == -1 || dp[j] < dp[min2]) {
                    min2 = j;
                }
            }

            int[] ndp = new int[k];
            for (int j = 0; j < k; j++) {
                int best = dp[min1];
                if (j == min1 && min2 != -1) {
                    best = dp[min2];
                }
                ndp[j] = costs[i][j] + best;
            }

            dp = ndp;
        }

        int answer = Integer.MAX_VALUE;
        for (int v : dp) {
            answer = Math.min(answer, v);
        }
        return answer;
    }
}

func minCostII(costs [][]int) int {
    if len(costs) == 0 {
        return 0
    }

    k := len(costs[0])
    dp := make([]int, k)

    for i := 0; i < len(costs); i++ {
        min1, min2 := -1, -1
        for j := 0; j < k; j++ {
            if min1 == -1 || dp[j] < dp[min1] {
                min2 = min1
                min1 = j
            } else if min2 == -1 || dp[j] < dp[min2] {
                min2 = j
            }
        }

        ndp := make([]int, k)
        for j := 0; j < k; j++ {
            best := dp[min1]
            if j == min1 && min2 != -1 {
                best = dp[min2]
            }
            ndp[j] = costs[i][j] + best
        }
        dp = ndp
    }

    answer := dp[0]
    for _, v := range dp {
        if v < answer {
            answer = v
        }
    }
    return answer
}

复杂度分析

时间复杂度：$O(nk)$，凭据是外层对 n 个房子各执行一次，内层只有两遍互不嵌套的长度为 k 的扫描——一遍求最小与次小，一遍生成新行——转移中原本对上一行颜色的枚举被这两个预先算好的极值取代了。

空间复杂度：$O(k)$，凭据是二维状态被滚动成一维，任意时刻只同时存在上一行的 dp 和当前行的 ndp 两个长度为 k 的数组，与房子数量 n 无关。

关键点总结

相邻元素之间的互斥约束加上单向推进的决策序列，就是逐位动态规划的标准信号；状态里只需要携带「上一步做了什么选择」，更早的历史可以全部丢弃。

当转移形如「在上一层所有状态中排除一个后取最小」时，维护最小值与次小值就能把内层枚举降成常数，这是一条可以直接搬到别处的优化模式。

记录极值时存下标而非数值，能同时回答「最小是多少」和「最小是谁」两个问题，在需要判断「当前决策是否与上一层最优决策冲突」时必不可少。

让滚动数组的初值恰好落在「零成本的虚拟第 -1 行」上，可以把首行初始化并入主循环，减少一处容易写错的特判——这类「虚拟起点」技巧在序列 DP 里非常通用。

新行必须写进独立数组，因为同一轮内所有转移都读的是上一行的完整快照，原地覆盖会让后写的列读到已被修改的值。

面试视角：面试官几乎一定会先让你写 $O(nk^2)$ 的朴素版，再问「k 很大怎么办」。答题时要主动点出「每个 j 的转移只是从同一个集合里挖掉一个元素」，然后自然引出最小/次小。如果还被追问空间，可以说明 ndp 也能省掉——用两个变量记住本行的新最小与新次小，边算边更新，把空间降到 $O(1)$。

易错点总结

内层判断写成 else if (dp[j] < dp[min2]) 却不先处理 min2 == -1：用例 k = 2 且 dp = [3, 5]，j = 1 时 min2 还是 -1，dp[-1] 直接抛数组越界。

更新最小值时忘记把旧最小挤给次小，写成 if (dp[j] < dp[min1]) min1 = j;：用例 dp = [5, 3, 1]，最终 min1 = 2、min2 停在 1（值 3），但真正的次小是 3 所在的列 1，此例侥幸对；换成 dp = [1, 3, 0] 则 min2 停在 1（值 3），而正确次小应是 1（列 0），转移会多花 2。

用数值而不是下标记录最小/次小，然后用 dp[j] == minVal 判断是否冲突：用例某行 dp = [2, 2, 7]，两列并列最小，j = 1 会被误判为「必须退让」而取次小 2，结果虽相同，但当 dp = [2, 2, 7] 且次小被错记为 7 时，j = 1 会多花 5。

原地更新 dp[j] = costs[i][j] + best 而不新建数组：用例 costs = [[1, 5, 3], [2, 9, 4]]，第二轮算完 dp[0] 后 dp 已被污染，后面列取到的 dp[min1] 是新值而非上一行的值，答案偏大。

把 dp 初始化为 costs[0] 之后主循环仍从 i = 0 开始：用例 costs = [[1, 5, 3]]，第一行被计入两次，返回 2 而非 1。

收尾时 Java 里用 int answer = 0 再取 Math.min：用例任意正开销输入如 [[1, 5, 3]]，min(0, 1) 恒为 0，直接返回 0。

忘记 costs.length == 0 的判断：用例 costs = []，costs[0].length 抛数组越界异常。

转移时对所有 j 一律取 dp[min1]，漏掉 j == min1 的退让：用例 costs = [[1, 5, 3], [2, 9, 4]]，第二轮 j = 0 会取 dp[0] = 1 得 3，最终返回 3，对应两间房都刷颜色 0，违反相邻不同色，正确答案是 5。

反过来对 j != min1 也用 dp[min2]：用例同上，第二轮 j = 2 取 dp[min2] = 3 得 7，答案变成 5 与 7 取小仍为 5 看不出问题；但在 costs = [[1, 100], [1, 1]] 上会让 j = 1 取到不必要的大值，返回 3 而非 2。

每轮在生成新行的循环内部才去找最小/次小：用例任意输入，读到的 dp 已经掺入部分新值（若原地写）或每次重复扫描（若不原地写），前者答案错误，后者复杂度退回 $O(nk^2)$，失去本解法的全部意义。

k = 1 且房子数大于 1 时仍去访问 dp[min2]：用例 costs = [[1], [2]]，min2 恒为 -1，若不写 min2 != -1 的保护会越界；加上保护后返回 3，虽不符合「相邻不同色」的现实语义，但题目数据不包含该情形，实现上只需保证不崩。

相似题目

题目	难度	考察点
256. 粉刷房子	中等	颜色数固定为 3，转移可以直接手写三项取小，无需极值优化
1473. 粉刷房子 III	困难	多出「恰好形成 target 个街区」的维度，状态要加一维段数
198. 打家劫舍	中等	相邻约束变成「不能同时选」而非「不能同值」，状态只有两种
931. 下降路径最小和	中等	转移只允许来自相邻三列，是本题约束的收紧版
746. 使用最小花费爬楼梯	简单	一维序列上的最小代价推进，考察起点与终点的边界处理