1681. 最小不兼容性

题目描述

给一个数组nums，数组里面有一些值，值可能会重复
再给一个k，需要把nums分配到k个子集中，每个子集没有相同元素，且所有子集的不兼容性之和最小？

基本分析

1. 明显不满足要求的有哪些？某个值的次数>k
2. 是不是存在贪心的思路？没有
3. 因为需要给每个子集放n//k个元素，这个要怎么放才能考虑比较好转移？用mask表示nums被选择的状态，sub是我们最后一个选择的子集，尝试枚举子集sub(需要满足1的个数是n//k的条件， 需要满足元素不重要求)。对每个sub计算不兼容性v[sub]，同时看mask^sub是不是存在，存在时f[mask^sub] + value[sub]就是一个潜在的值；多个sub对应的以上结果取min就是f[mask]
4. 根据以上的转移思路，需要做哪些预处理？预处理出所有满足条件的sub对应的不相容值value[sub];具体怎么实现？
   • 在1<<n范围内进行遍历，找到1个个数是n//k的sub
   • 在n的范围内遍历sub的1处的索引，追加索引对应的值到集合，如果集合重复，这个sub不满足要求；如果不重复，遍历完索引后，在更新将对应的不兼容性存在value[sub]中
5. 定义dp结构和初始化边界注意什么？可能很多mask是不能满足要求的，这里吧f定义成了字典；当mask不选的时候，不兼容值是0，f[0]=0
6. dp过程的思路？
   • 还是在1<<n范围内遍历mask，对mask的要求是1的个数需要是n//k的倍数，不满足的直接跳过
   • 为了减少枚举的复杂度，在mask的子集比value长度少的时候选择枚举mask子集转移；当mask子集长度比value长时候，枚举value的k和v进行转移
     • 前者的时候，先找出mask的子集sub，sub初值时mask，如果要转移需要满足sub在value中且mask^sub在f中，如果满足条件，说明是一种合理方式，可以用来转移mask，到底小不小再说；不管能不能成立，继续便利sub直到sub=0
     • 后者的时候，直接枚举value的键-值：sub-v。对sub的要求是sub是mask的子集（mask&sub=sub）, 且mask^sub能转移；后面步骤和以上类似
7. 最后的结果？f[(1<<n)-1]是不是存在

代码

class Solution:
    def minimumIncompatibility(self, nums: List[int], k: int) -> int:
        n = len(nums)
        if n == k:
            return 0
        most = Counter(nums).most_common()[0][1]
        if most > k:
            return -1
        
        # 预处理1个数为n//k子集对应的不兼容性
        value = dict()
        for sub in range(1<<n):
            if bin(sub).count('1') != n//k:
                continue
            flag = True
            freq = set()
            for j in range(n):
                if sub & (1<<j):
                    if nums[j] in freq:
                        flag = False
                        break
                    freq.add(nums[j])
            if flag:
                value[sub] = max(freq) - min(freq)
        
        # 处理dp
        f = dict()
        f[0] = 0
        for mask in range(1, 1<<n):
            if bin(mask).count('1') % (n//k) != 0:
                continue
            if 2**(bin(mask).count('1')) < len(value):
                sub = mask
                while sub > 0:
                    if sub in value and mask ^ sub in f:
                        if mask not in f:
                            f[mask] = f[mask ^ sub] + value[sub]
                        else:
                            f[mask] = min(f[mask], f[mask ^ sub] + value[sub])
                    sub = (sub-1) & mask
            else:
                for sub, v in value.items():
                    if sub & mask == sub and mask ^ sub in f:
                        if mask not in f:
                            f[mask] = f[mask^sub] + value[sub]
                        else:
                            f[mask] = min(f[mask], f[mask^sub]+value[sub])
        
        return f[(1<<n)-1] if (1<<n)-1 in f else -1

复杂度

时间：\(枚举子集合需要O(3^n)\)
空间：\(O(2^n)\)

总结

这个题目的特点是当前数组中的数字的选择与否可以用二进制的mask表示，但是比较难想到怎么去实现转移？这个时候我们就要去考虑用一个mask的子集sub表示选择的最后一个子集的选择情况。因为题目中给了要求，这个sub就要满足（个数+不重的），对某个mask和其中一个合理的sub，f[mask^sub]+value[sub]就一种可能的转移，最后是不是最小，还要结合多个可能的sub去看。
为什么需要考虑预处理？在转移的时候去找value[sub]就可能太晚了，而且先处理完把结果写成字典，后面直接用就行。考虑怎么存结果？就是常见的枚举sub，对sub的长度和值的选择做删选，满足条件的把对应的不兼容性存下来
转移时候的思路也比较常见，就是遍历mask，不考虑不满足1长度要求的mask。对mask考虑转移的时候，需要枚举子集sub，需要看能不能从之前的状态f[mask^sub]转移，所以对sub和mask^sub都有要求。另外考虑复杂度，对mask子集少的时候，考虑的是枚举mask的子集，对子集多的时候，考虑的是枚举value。