LeetCode 1681. 最小不兼容性

约 9 分钟
文章信息 6 个分类 5 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 B站
标签
数组 哈希表 动态规划 位运算 位掩码

题目描述

✅ 1681. 最小不兼容性

image-20260929090828282

image-20260929090828389

题意分析

将全部元素分成 k 个组，每组恰好有 m=n/k 个元素，同组不能出现相同数值。每组的费用是最大值减最小值，求总费用最小值，无法分组时返回 -1。分组不要求连续，但每个数组位置必须且只能使用一次；题目保证 n 能被 k 整除。

解法：状态压缩 DP

核心思路

[!blue]
用已使用下标集合表示状态，一次加入一个完整组。 mask 的第 i 位表示下标 i 是否已使用，dp[mask] 保存搜索中把这些元素组成若干合法完整组的最小费用。组数等于已用元素数除以 m，无需另加一维；未用元素及后续可选组只由 mask 决定，因此相同状态只保留最小费用即可。

先预处理每个子集的 cost[sub]。只有子集包含恰好 m 个下标、且对应数值互不重复时，它才能成为一组，费用为最大值减最小值；其他子集记为 -1。掩码区分的是不同位置，即使两个位置值相等也有不同位，组内是否同值必须另外用 seen 判断。

对可达状态，剩余下标是 remain = all ^ mask。枚举其中的合法子集 sub，执行 dp[mask | sub] = min(dp[mask | sub], dp[mask] + cost[sub])。新组与已用元素不重叠，又恰好包含 m 项，转移后仍是由若干完整组组成的合法状态。

分组没有先后区别，可以强制下一组包含剩余的最小下标。任意完整划分中都恰好有一组包含这个下标，把它先处理不会改变总费用；剩余部分继续采用同样规则，所以这项限制只消除组顺序的重复，不会漏掉最优划分。

每次加入非空子集都会令新掩码大于旧掩码，因此按掩码递增处理时，所有转移来源都已经计算完成。到达 all 后恰好使用全部 n 个元素，每组又固定为 m 项，也就恰好完成了 k 组。

解题步骤

  1. 统计每个数值的次数；同值元素每组最多放一个，若出现次数超过 k，立即返回 -1。
  2. 枚举所有掩码，筛选大小为 m 且数值不重复的子集，计算其费用。
  3. 初始化 dp[0]=0，其余为不可达标记；按掩码递增扫描，跳过不可达状态和全集状态。
  4. 找到 remain 的最低有效位，用 sub=(sub-1)&remain 依次枚举非空子集，只用包含该位且 cost[sub] 合法的组进行转移。
  5. dp[all] 仍不可达则返回 -1，否则返回这个最小总费用。

k=n 时每组只有一个元素，费用都为 0；k=1 时只能使用整个数组作为一组，重复值会使它不合法。题目数值范围为 1..n，所以按值计数和判重的数组都分配 n+1 个位置。

代码实现

class Solution {
    public int minimumIncompatibility(int[] nums, int k) {
        int n = nums.length;
        int m = n / k;
        int all = (1 << n) - 1;

        int[] frequency = new int[n + 1];

        for (int value : nums) {
            // 每组最多容纳一个同值元素，出现超过组数必然无解。
            if (++frequency[value] > k) {
                return -1;
            }
        }

        // 预处理每个候选小组的代价，-1 表示大小不符或组内有重复值。
        int[] cost = new int[1 << n];

        Arrays.fill(cost, -1);

        for (int mask = 0; mask <= all; mask++) {
            if (Integer.bitCount(mask) != m) {
                continue;
            }

            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            boolean ok = true;
            // 掩码区分下标，这里另外按数值判定组内重复。
            boolean[] seen = new boolean[n + 1];

            for (int i = 0; i < n; i++) {
                if (((mask >> i) & 1) == 0) {
                    continue;
                }

                int v = nums[i];

                if (seen[v]) {
                    ok = false;
                    break;
                }

                seen[v] = true;
                min = Math.min(min, v);
                max = Math.max(max, v);
            }

            if (ok) {
                cost[mask] = max - min;
            }
        }

        // 未能组成完整小组的状态保持不可达。
        int inf = Integer.MAX_VALUE / 4;
        int[] dp = new int[1 << n];

        Arrays.fill(dp, inf);
        dp[0] = 0;

        for (int mask = 0; mask <= all; mask++) {
            if (dp[mask] == inf) {
                continue;
            }

            if (mask == all) {
                continue;
            }

            int remain = all ^ mask;
            // 固定下一组必须包含的下标，避免重复考虑组的处理顺序。
            int first = 0;

            while (((remain >> first) & 1) == 0) {
                first++;
            }

            int must = 1 << first;

            for (int sub = remain; sub > 0; sub = (sub - 1) & remain) {
                if ((sub & must) == 0) {
                    continue;
                }

                if (cost[sub] == -1) {
                    continue;
                }

                int nxt = mask | sub;
                // 加入一个完整合法组，未来状态只依赖新的已用下标集合。
                int cand = dp[mask] + cost[sub];

                if (cand < dp[nxt]) {
                    dp[nxt] = cand;
                }
            }
        }

        if (dp[all] == inf) {
            return -1;
        }

        return dp[all];
    }
}

import "math/bits"

func minimumIncompatibility(nums []int, k int) int {
    n := len(nums)
    m := n / k
    all := (1 << n) - 1

    frequency := make([]int, n+1)
    for _, value := range nums {
        frequency[value]++
        // 每组最多容纳一个同值元素，出现超过组数必然无解。
        if frequency[value] > k {
            return -1
        }
    }

    // 预处理每个候选小组的代价，-1 表示大小不符或组内有重复值。
    cost := make([]int, 1<<n)
    for i := 0; i < len(cost); i++ {
        cost[i] = -1
    }
    for mask := 0; mask <= all; mask++ {
        if bits.OnesCount(uint(mask)) != m {
            continue
        }
        minVal := int(^uint(0) >> 1)
        maxVal := -minVal
        // 掩码区分下标，这里另外按数值判定组内重复。
        seen := make([]bool, n+1)
        ok := true
        for i := 0; i < n; i++ {
            if (mask>>i)&1 == 0 {
                continue
            }
            v := nums[i]
            if seen[v] {
                ok = false
                break
            }
            seen[v] = true
            if v < minVal {
                minVal = v
            }
            if v > maxVal {
                maxVal = v
            }
        }
        if ok {
            cost[mask] = maxVal - minVal
        }
    }

    // 未能组成完整小组的状态保持不可达。
    inf := int(^uint(0)>>1) / 4
    dp := make([]int, 1<<n)
    for i := 0; i < len(dp); i++ {
        dp[i] = inf
    }
    dp[0] = 0

    for mask := 0; mask <= all; mask++ {
        if dp[mask] == inf || mask == all {
            continue
        }
        remain := all ^ mask
        // 固定下一组必须包含的下标，避免重复考虑组的处理顺序。
        first := 0
        for ((remain >> first) & 1) == 0 {
            first++
        }
        must := 1 << first
        for sub := remain; sub > 0; sub = (sub - 1) & remain {
            if (sub & must) == 0 {
                continue
            }
            if cost[sub] == -1 {
                continue
            }
            nxt := mask | sub
            // 加入一个完整合法组，未来状态只依赖新的已用下标集合。
            cand := dp[mask] + cost[sub]
            if cand < dp[nxt] {
                dp[nxt] = cand
            }
        }
    }

    if dp[all] == inf {
        return -1
    }
    return dp[all]
}

复杂度分析

  • 时间复杂度：$O(n·2^n+3^n)$。预处理每个子集最多检查 $n$ 个位置；转移时，每个位置可属于已用集合、当前新组、仍未用集合三种情况，所有状态与子集组合总数以 $3^n$ 为上界。
  • 空间复杂度：$O(2^n)$，保存合法组费用和状态表。

关键点总结

[!green]

  • 掩码按下标表示使用情况，合法性按数值判重。
  • 每次转移一个完整组，状态无需保存半组信息。
  • 固定下一组必含的下标只消除顺序对称，不改变最小值。

易错点总结

[!yellow]

  • 把非法 cost 初始化为零：会接受大小错误或含重复值的组。
  • 子集循环包含零且继续递推：零的下一个子集会回到全集，造成循环。
  • 按倒序只扫描一次状态：刚更新的较大状态没有机会继续扩展。
  • 判重数组只开 n 项：数值可以为 n，需要 n+1 个位置。

相似题目

题目 难度 关联与区别
698. 划分为k个相等的子集 中等 同样把所有元素分组，本题固定每组人数、禁止组内重复并最小化极差和，而非要求各组和相同。
1799. N 次操作后的最大分数和 困难 同样可预处理合法小组并用位掩码DP合并不相交组，原题固定每组两项并按操作次序加权gcd计分。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/61696976
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！