LeetCode 265. 粉刷房子 II

2023-05-03 HGNULB 约 5 分钟

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

分类

LeetCode CodeTop 困难未解决会员题 2-5 字节阿里

题目描述

✅ 265. 粉刷房子 II

题意分析

为一排房子分别选择一种颜色，costs[i][j] 是第 i 间房刷成颜色 j 的费用。所有房子都要刷，相邻房子不能同色，求最小总费用；不相邻的房子可以使用相同颜色。

解法：DP + 最小二值

核心思路

[!blue]

处理当前房子之前，令 dp[j] 表示此前房子全部刷完、且最后一间颜色为 j 的最小费用。若当前房子选颜色 j，上一间可以选任意 t != j，所以新费用为 costs[i][j] + min(dp[t])，其中最小值只能从其他颜色中取。

这个状态足够描述后续限制，因为当前房子只与紧邻的上一间冲突。固定上一间颜色后，更早房子的安排只影响总费用，保留最小费用即可。枚举所有可用前驱颜色，便覆盖了当前颜色的全部合法方案。

若为每个当前颜色重新扫描前驱，一行要花 $O(k^2)$。实际只排除一个颜色，因此先找出旧 dp 中最小、次小费用所在的两个不同下标 min1、min2：当前颜色不是 min1 时直接取最小值；当前颜色恰为 min1 时，排除它后最小的就是 min2。

次小是“另一个颜色下标中的最小费用”，数值允许与最小值相等。扫描时若发现新的最小值，旧最小必须退到次小；否则只需尝试更新次小。这保证排除任何一个颜色后，都能用两个下标之一找到最佳前驱。

初始 dp 全为 0，表示尚未粉刷的费用，第一间房转移后自然得到各颜色自身成本。每行先完整计算 ndp，再替换旧 dp，避免同一轮混用新旧状态。所有房子处理完后，最后一间颜色不限，返回 dp 中的最小值。

解题步骤

空费用表直接返回 0；否则创建长度为颜色数 k 的零数组 dp。

每处理一间房，扫描旧 dp，求出最小和次小费用的不同颜色下标。

对每个当前颜色，选择不与它冲突的最优前驱，再加本行成本，写入 ndp。

令 dp = ndp，继续处理下一间房。

返回最后一行所有颜色费用中的最小值。

代码实现

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)$，同时保存旧行与新行。

关键点总结

[!green]

两个极值来自不同颜色，但费用可以相等，不能只保存两个不同的费用数值。

发现新最小时，原最小要退到次小位置。

易错点总结

[!yellow]

当前颜色与最小位置相同仍用最小，会允许相邻同色。

最小更新却不保留旧最小，可能丢掉真正次小。

尚在读取旧行时原地覆盖，会将新旧费用混用。

相似题目

题目	难度	关联与区别
256. 粉刷房子	中等	从三种颜色扩展到k种，为每个颜色枚举前一行所有其他颜色会多一层循环。
1289. 下降路径最小和 II	困难	同样要求相邻层不能选同一列，可通过上一层最小与次小值快速转移。
1473. 粉刷房子 III	困难	粉刷房子系列。II 处理任意颜色数，III 还需保留预着色结果，并限制连续同色街区的数量。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2023/83373424

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！