LeetCode 1681. 最小不兼容性

2022-09-01 HGNULB 约 15 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 1681. 最小不兼容性

题意分析

把 nums 分成 k 个大小完全相同的子集，每个子集的不兼容性定义为它的最大值减最小值，要求所有子集不兼容性之和最小；分不出来就返回 -1。

「大小完全相同」这条约束把每组的容量钉死为 $m = n / k$，n 能被 k 整除是题目保证的。这意味着分组不是自由切割，而是把 n 个元素恰好摊进 k 个 m 元格子。

无解只有一个来源：同一个子集里不能出现重复元素（否则最大最小之差的定义仍然成立，但题目明确要求子集内元素互不相同）。所以若某个数值出现的次数超过 k，它无论怎么分都会有两个落进同一组，直接无解。

决定做法的是数据规模：n 最多 16，元素值也不超过 n。16 这个数字几乎是「状态压缩」的代名词——$2^{16} = 65536$ 个子集状态完全可以枚举，而 $16!$ 的排列数则不可接受。元素值上界很小这一点，则让「子集内是否有重复」可以用一个小数组直接判定。

还要注意的是分组之间没有顺序：把元素分成 ${A, B}$ 和分成 ${B, A}$ 是同一种方案。如果不消除这种对称性，搜索空间会被放大 $k!$ 倍。

边界包括：k == 1（整个数组是一组，答案是全局极差，但若有重复元素则无解）；k == n（每组一个元素，不兼容性全为 0）；以及某个值出现次数超过 k 的无解情形。

解法：状态压缩 DP

核心思路

暴力做法是枚举所有分组方案：把 n 个元素划分成 k 个大小为 m 的无序组，方案数是 $\dfrac{n!}{(m!)^k \cdot k!}$，n = 16、k = 2 时约 6435，看着不大；但 k = 4、m = 4 时已经是 262 万，k = 8 时更糟，而且每个方案还要计算代价。真正的问题是这种枚举没有复用性——不同方案之间共享的前缀被反复重算。

观察点在于：当我们已经组好了若干完整的组，接下来怎么组，只取决于「还剩哪些元素没用」，与已用元素被怎样分组无关。这就是无后效性，也是把指数枚举换成 DP 的依据。而「还剩哪些元素」在 n ≤ 16 时正好可以用一个 16 位整数表示。

于是定义状态：dp[mask] 表示已经选取 mask 中标记的这些元素、并把它们恰好分成若干个满员小组时，这些小组的不兼容性之和的最小值。mask 中 1 的个数必然是 m 的倍数，其他 mask 不可达。初始状态 dp[0] = 0（还没组任何小组，代价为 0），答案是 dp[all]，all 是全 1 掩码；若它仍是无穷大，说明无解。

转移是「一次补齐一个完整小组」：从 dp[mask] 出发，在剩余元素 remain = all ^ mask 中挑一个大小为 m 的子集 sub 作为新的一组，转移到 dp[mask | sub]，代价加上 cost[sub]。

cost[sub] 是预处理量，含义是「把 sub 中的元素放在同一组时的不兼容性」。只有当 sub 恰好有 m 个元素且其中的数值互不相同时它才有定义，否则标记为非法。把它预处理出来，是因为同一个 sub 会在无数条转移路径上被用到，重复计算是纯浪费。

消除组间顺序的对称性靠一个小技巧：强制新的一组必须包含 remain 中最低位的那个元素。任何一种分组方案里，含有「当前剩余的最小下标元素」的那一组是唯一的，把它钉死为「下一个要组的组」，就让每种方案在 DP 中只被计数一次。这一步既是正确性无关的优化，也把枚举量从 $3^n$ 砍掉一半以上。

解题步骤

先统计数值频次。若任一数值出现超过 k 次，k 个组无法各自最多放一个，直接返回 -1。

算出每组容量 m = n / k 与全集掩码 all = (1 << n) - 1。后续所有判断都围绕这两个量展开。

预处理 cost 数组，长度 $2^n$，初值全置 -1 表示非法。遍历每个 mask，先用位计数过滤掉大小不等于 m 的；再遍历其中的每一位，用一个按数值索引的布尔数组检测重复，一旦发现重复立即标记非法并跳出；同时统计最大值与最小值。合法则写入 max - min。数值上界不超过 n ≤ 16，所以布尔数组开到 21 已经绰绰有余。

初始化 dp 数组，长度 $2^n$，全部置为一个足够大的哨兵值，dp[0] = 0。哨兵取 Integer.MAX_VALUE / 4 而不是 MAX_VALUE，是为了给后续的 dp[mask] + cost[sub] 留出加法空间，避免溢出成负数后被误当作更优解。

正序遍历所有 mask 做转移。正序保证在处理 mask 时，所有能到达它的更小状态都已经算完——因为 mask | sub 严格大于 mask（sub 与 mask 无交集且非空）。遇到 dp[mask] 仍是哨兵值就跳过，不可达状态不能继续扩展，否则会把哨兵值当成真实代价传播出去。

找出 remain 的最低位 must。这是对称性消除的落点：接下来枚举的子集必须包含它。

用 sub = remain; sub > 0; sub = (sub - 1) & remain 枚举 remain 的所有非空子集。这是子集枚举的标准写法，(sub - 1) & remain 能不重不漏地给出下一个子集。枚举体内先跳过不含 must 的、再跳过 cost 为 -1 的（既排除了大小不对，也排除了含重复值的），然后用 dp[mask] + cost[sub] 更新 dp[mask | sub]。

最后检查 dp[all]：等于哨兵值说明全集不可达，返回 -1；否则返回它。

以 nums = [1, 2, 1, 4]、k = 2 走一遍，预期答案 4。n = 4，m = 2，all = 0b1111。

预处理阶段，只有大小为 2 的掩码有资格。下标 0、2 上的值都是 1，所以掩码 0b0101 含重复，非法。其余大小为 2 的掩码：0b0011（值 1、2）代价 1；0b1001（值 1、4）代价 3；0b0110（值 2、1）代价 1；0b1010（值 2、4）代价 2；0b1100（值 1、4）代价 3。

DP 从 dp[0] = 0 开始。remain = 0b1111，最低位是第 0 位，must = 0b0001。含 must 且大小为 2 的合法子集有 0b0011（代价 1）、0b1001（代价 3）；0b0101 因含重复被跳过。于是 dp[0b0011] = 1、dp[0b1001] = 3。

处理 mask = 0b0011 时 remain = 0b1100，最低位是第 2 位，must = 0b0100。含它的合法二元子集只有 0b1100，代价 3，于是 dp[0b1111] = 1 + 3 = 4。处理 mask = 0b1001 时 remain = 0b0110，must = 0b0010，合法子集是 0b0110，代价 1，于是 dp[0b1111] 尝试更新为 $3 + 1 = 4$，与已有值相同不变。

最终 dp[0b1111] = 4，对应分组 {1, 2} 与 {1, 4}，不兼容性 $1 + 3 = 4$。

再看无解用例 nums = [1, 1, 1, 1]、k = 2。所有大小为 2 的掩码都含两个 1，cost 全为 -1，从 dp[0] 出发一个转移都做不出来，dp[all] 保持哨兵值，返回 -1。

代码实现

import java.util.Arrays;

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 \cdot 2^n + 3^n)$。预处理部分对每个掩码扫一遍所有位，是 $O(n \cdot 2^n)$；DP 部分对每个 mask 枚举 remain 的全部子集，所有 (mask, sub) 组合的总数是 $\sum_{mask} 2^{ remain } = 3^n$，这是子集枚举的经典结论。n = 16 时 $3^{16} \approx 4.3 \times 10^7$，加上「必含最低位」的剪枝实际只有一半左右，可以通过。

空间复杂度：$O(2^n)$，cost 与 dp 两个数组各占 $2^n$ 个整数，n = 16 时约 65536 项，内存压力很小。预处理中的 seen 数组是常数大小。

关键点总结

n ≤ 16 加「划分成若干组」几乎是状态压缩 DP 的固定搭配。看到这个规模就应该先想「用二进制表示已用元素集合」，而不是先想搜索或贪心。

同一数值出现超过 k 次时必然无解，因为 k 个组每组最多容纳一个；代码先做这个必要条件检查，合法子集预处理仍负责保证每个具体组内无重复。

状态定义的关键是找到无后效性的切口：本题的切口是「已用元素集合」，因为未来的选择只依赖剩下哪些元素，不依赖已用元素的分组方式。能说清这一点，状态就定对了一半。

把「一次转移补齐一整个组」而不是「一次转移放一个元素」，能让状态里不必额外记录「当前组已放几个」，维度更低。这是划分类状压题的通用取舍。

强制新组包含剩余最低位是消除组间顺序对称性的标准手法。它不改变最优值，却能把等价方案压成一条路径，既提速又避免重复统计。同类技巧在 698、473 里也反复出现。

预处理把「子集合法性 + 代价」一次算清，让 DP 主循环只剩查表和取最小值。哪些量该预处理，判断标准是「它是否会在多条转移路径上被重复计算」。

哨兵值要留出加法余量。用 MAX_VALUE 做无穷大时，dp[mask] + cost[sub] 会溢出成负数并被误判为更优，这是状压 DP 里最隐蔽的一类错误。

面试视角：先说清「暴力枚举划分方案的数量」，再指出无后效性并给出状态定义，然后讲转移和子集枚举写法，最后补上对称性消除与哨兵细节。面试官常追问「为什么复杂度是 $3^n$」，要能给出「每个元素在 mask 内、在 sub 内、都不在，共三种归属」的组合论证；再追问「能不能改成按元素逐个放」，答案是可以，但状态要加一维记录当前组已放个数，转移更琐碎。

易错点总结

错误写法：哨兵值取 Integer.MAX_VALUE。用例 nums = [1, 1, 1, 1]、k = 2 → 虽然本例转移不会发生，但只要有任何一条从不可达状态出发的转移被执行，MAX_VALUE + cost 立刻溢出成负数并被当作最优解写入 dp，最终返回一个负的不兼容性。

错误写法：不跳过 dp[mask] == inf 的不可达状态。用例 nums = [1, 2, 1, 4]、k = 2 → 从 dp[0b0101]（含重复值、本不可达）继续扩展，哨兵值一路传播，配合前一条的溢出会直接给出错误答案。

错误写法：省略「新组必须包含 remain 最低位」的限制。用例 nums = [1, 2, 1, 4]、k = 2 → 结果仍然正确，但每种分组被按 k! 种顺序重复枚举，n = 16、k = 8 时运行时间成倍增长，大用例超时。

错误写法：子集枚举写成 for (int sub = remain; sub >= 0; sub = (sub - 1) & remain)。用例：任意输入 → sub 减到 0 后 (0 - 1) & remain 又回到 remain，条件 sub >= 0 恒成立，程序陷入死循环。

错误写法：判重时用「下标是否重复」而不是「数值是否重复」。用例 nums = [1, 1, 1, 1]、k = 2 → 每个掩码里的下标天然互不相同，所有子集都被判为合法，返回 0，正确答案是 -1。

错误写法：seen 数组按元素值开成 new boolean[n]。用例 nums = [1, 2, 3, 4]、k = 2 → 值 4 作为下标访问长度为 4 的数组，越界抛异常；数值上界是 n，数组长度至少要 n + 1。

错误写法：cost 数组初值设为 0 而不是 -1。用例 nums = [1, 1, 1, 1]、k = 2 → 含重复值的子集代价被当成 0，DP 顺利走到全集，返回 0，正确答案是 -1。

错误写法：转移时不校验 sub 的大小是否为 m。用例 nums = [1, 2, 1, 4]、k = 2 → 若 cost 又恰好对非 m 大小的子集有值，会拼出大小不等的分组，答案偏小且不满足「每组大小相同」。

错误写法：mask 倒序遍历。用例 nums = [1, 2, 1, 4]、k = 2 → 处理 0b1111 时它的前驱 0b0011 还未被更新，dp[all] 拿不到任何有效转移，返回 -1，正确答案是 4。

错误写法：把答案写成 dp[all] 但忘记判断它是否仍是哨兵值。用例 nums = [1, 1, 1, 1]、k = 2 → 返回一个巨大的哨兵数字而不是 -1。

错误写法：通过频次检查后直接返回 0。频次不超过 k 只说明可以避免组内重复，不能给出最小代价；nums = [1,2,1,4]、k = 2 通过检查，但最小不兼容性是 4 而不是 0。

相似题目

题目	难度	考察点
78. 子集	中等	用二进制枚举子集的入门形态，只需构造不需优化，是本题预处理环节的基础
416. 分割等和子集	中等	只分两组且只关心和，可用容量维度的 01 背包，无需压缩到集合状态
473. 火柴拼正方形	中等	固定分四组且要求组内和相等，可用回溯加剪枝，也可用同样的状压 DP 骨架
698. 划分为k个相等的子集	中等	与本题结构最接近，只是评价标准从极差换成「和是否相等」，可用同一套掩码 DP
368. 最大整除子集	中等	同样在子集上做最优化，但元素规模大，只能靠排序后的线性 DP 而非状态压缩
847. 访问所有节点的最短路径	困难	状态是「已访问集合 + 当前位置」，展示状压如何与图上 BFS 结合
51. N 皇后	困难	用位运算维护列与两条对角线的占用，是位掩码用于剪枝而非用于 DP 状态
1526. 形成目标数组的子数组最少增加次数	困难	同为「最小操作次数」但结构完全不同，靠差分与贪心一遍扫描解决