01. 状态压缩 DP 知识

ITCharge大约 13 分钟

状态压缩 DP 知识

1. 状态压缩 DP 简介

状态压缩 DP：简称为「状压 DP」，是一种应用在「小规模数据」的数组 / 字符串上，结合「二进制」的性质来进行状态定义与状态转移的动态规划方法。

我们曾在「位运算知识」章节中，学习过「二进制枚举子集算法」。这里先来回顾一下如何通过二进制枚举子集。

1.1 二进制枚举子集

对于一个元素个数为 $n$ 的集合 $S$ 来说，每一个位置上的元素都有选取和未选取两种状态。我们可以用数字 $1$ 来表示选取该元素，用数字 $0$ 来表示不选取该元素。

那么我们就可以用一个长度为 $n$ 的二进制数来表示集合 $S$ 或者表示 $S$ 的子集。其中二进制的每一个二进位都对应了集合中某一个元素的选取状态。对于集合中第 $i$ 个元素来说，二进制对应位置上的 $1$ 代表该元素被选取， $0$ 代表该元素未被选取。

举个例子，比如长度为 $5$ 的集合 $S = \lbrace 5, 4, 3, 2, 1 \rbrace$ ，我们可以用一个长度为 $5$ 的二进制数来表示该集合。

比如二进制数 $11111_{(2)}$ 就表示选取集合的第 $1$ 位、第 $2$ 位、第 $3$ 位、第 $4$ 位、第 $5$ 位元素，也就是集合 $\lbrace 5, 4, 3, 2, 1 \rbrace$ ，即集合 $S$ 本身。如下表所示：

集合 S 中元素位置	5	4	3	2	1
对应选取状态	选取	选取	选取	选取	选取
二进位对应值	1	1	1	1	1

再比如二进制数 $10101_{(2)}$ 就表示选取集合的第 $1$ 位、第 $3$ 位、第 $5$ 位元素，也就是集合 $\lbrace 5, 3, 1 \rbrace$ 。如下表所示：

集合 S 中元素位置	5	4	3	2	1
对应选取状态	选取	未选取	选取	未选取	选取
二进位对应值	1	0	1	0	1

再比如二进制数 $01001_{(2)}$ 就表示选取集合的第 $1$ 位、第 $4$ 位元素，也就是集合 $\lbrace 4, 1 \rbrace$ 。如下标所示：

集合 S 中元素位置	5	4	3	2	1
对应选取状态	未选取	选取	未选取	未选取	选取
二进位对应值	0	1	0	0	1

通过上面的例子我们可以得到启发：对于长度为 $5$ 的集合 $S$ 来说，我们只需要从 $00000 \sim 11111$ 枚举一次（对应十进制为 $0 \sim 2^5 - 1$ ）即可得到长度为 $5$ 的集合 $S$ 的所有子集。

我们将上面的例子拓展到长度为 $n$ 的集合 $S$ 。可以总结为：

对于长度为 $n$ 的集合 $S$ 来说，只需要枚举 $0 \sim 2^n - 1$ （共 $2^n$ 种情况），即可得到集合 $S$ 的所有子集。

1.2 状态定义与状态转移

1.2.1 状态定义

在状压 DP 中，我们通常采用二进制数的形式来表示一维状态，即集合中每个元素的选取情况。

和「二进制枚举子集算法」一样，我们通过一个「 $n$ 位长度的二进制数」来表示「由 $n$ 个物品所组成的集合中所有物品的选择状态」。

二进制数的每一个二进位都对应了集合中某一个元素的选取状态。如果该二进制数的第 $i$ 位为 $1$ ，说明集合中第 $i$ 个元素在该状态中被选取。反之，如果该二进制的第 $i$ 位为 $0$ ，说明集合中第 $i$ 个元素在该状态中没有被选取。

1.2.1 状态转移

一般来说，状压 DP 的状态转移方式有两种：

枚举子集：对于一个状态，枚举它的所有子集，或者枚举所有元素位置，找到比当前状态少选一个元素的子集。然后根据子集的值和状态之间的关系，更新当前状态的值。
枚举超集：对于一个状态，枚举它的所有超集。然后根据超集的值和状态之间的关系，更新当前状态的值。

其中，最常用的是「枚举子集」的方式。

1.3 状压 DP 的使用条件

对于元素个数不超过 $n$ 的集合来说，一共会出现 $2^n$ 个状态数量。因为在 $n$ 变大时会呈现指数级增长，所以状态压缩 DP 只适用于求解小数据规模问题（通常 $n \le 20$ ）。当 $n$ 过大时，使用状态压缩 DP 可能会超时。

2. 状态压缩 DP 中常用的位运算

在状压 DP 中，一维状态是集合，对状态进行操作或者状态之间进行转移，也就是要对集合进行操作。

因为我们使用二进制数来定义集合状态，所以对集合进行操作，就是对二进制数进行位运算操作。

如下所示，其中 $n$ 为集合中的元素个数， $A$ 、 $B$ 为两个集合对应的二进制数， $i$ 表示某个元素位置。

总状态数量：1 << n
在集合 $A$ 中加入第 $i$ 位元素（将二进制数第 $i$ 位赋值为 $1$ ）：A = A | (1 << i)
在集合 $A$ 中删除第 $i$ 位元素（将二进制数第 $i$ 位赋值为 $0$ ）：A = A & ~(1 << i)
判断集合 $A$ 是否选取了第 $i$ 位元素（判断二进制数第 $i$ 位是否为 $1$ ）：if A & (1 << i): 或者 if (A >> i) & 1:
将集合 $A$ 设置为空集：A = 0
将集合 $A$ 设置为全集：A = 1 << n - 1
求集合 $A$ 的补集：A = A ^ ((1 << n) - 1)
求集合 $A$ 与集合 $B$ 的并集：A | B
求集合 $A$ 与集合 $B$ 的交集：A & B

枚举集合 $A$ 的子集（包含 $A$ ）：

subA = A						# 从集合 A 开始
while subA > 0:					
    ...
    subA = (subB - 1) & A		# 获取下一个子集

枚举全集的所有子集：

for state in range(1 << n):		# state 为子集
    for i in range(n):			# 枚举第 i 位元素
        if (state >> i) & i:	# 如果第 i 位元素对应二进制位 1，则表示集合中选取了该元素
            ...

3. 状态压缩 DP 的应用

3.1 两个数组最小的异或值之和

3.1.2 题目大意

描述：给定两个整数数组 $nums1$ 和 $nums2$ ，两个数组长度都为 $n$ 。

要求：将 $nums2$ 中的元素重新排列，使得两个数组的异或值之和最小。并返回重新排列之后的异或值之和。

说明：

两个数组的异或值之和： $(nums1[0] \oplus nums2[0]) + (nums1[1] \oplus nums2[1]) + ... + (nums1[n - 1] \oplus nums2[n - 1])$ （下标从 $0$ 开始）。
举个例子， $[1, 2, 3]$ 和 $[3,2,1]$ 的异或值之和等于 $(1 \oplus 3) + (2 \oplus 2) + (3 \oplus 1) + (3 \oplus 1) = 2 + 0 + 2 = 4$ 。
$n == nums1.length$ 。
$n == nums2.length$ 。
$1 \le n \le 14$ 。
$0 \le nums1[i], nums2[i] \le 10^7$ 。

示例：

示例 1：

输入：nums1 = [1,2], nums2 = [2,3]
输出：2
解释：将 nums2 重新排列得到 [3,2] 。
异或值之和为 (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2。

示例 2：

输入：nums1 = [1,0,3], nums2 = [5,3,4]
输出：8
解释：将 nums2 重新排列得到 [5,4,3] 。
异或值之和为 (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8。

3.1.3 解题思路

思路 1：状态压缩 DP

由于数组 $nums2$ 可以重新排列，所以我们可以将数组 $nums1$ 中的元素顺序固定，然后将数组 $nums1$ 中第 $i$ 个元素与数组 $nums2$ 中所有还没被选择的元素进行组合，找到异或值之和最小的组合。

同时因为两个数组长度 $n$ 的大小范围只有 $[1, 14]$ ，所以我们可以采用「状态压缩」的方式来表示 $nums2$ 中当前元素的选择情况。

「状态压缩」指的是使用一个 $n$ 位的二进制数 $state$ 来表示排列中数的选取情况。

如果二进制数 $state$ 的第 $i$ 位为 $1$ ，说明数组 $nums2$ 第 $i$ 个元素在该状态中被选取。反之，如果该二进制的第 $i$ 位为 $0$ ，说明数组 $nums2$ 中第 $i$ 个元素在该状态中没有被选取。

举个例子：

$nums2 = \lbrace 1, 2, 3, 4 \rbrace, state = (1001)_2$ ，表示选择了第 $1$ 个元素和第 $4$ 个元素，也就是 $1$ 、 $4$ 。
$nums2 = \lbrace 1, 2, 3, 4, 5, 6 \rbrace, state = (011010)_2$ ，表示选择了第 $2$ 个元素、第 $4$ 个元素、第 $5$ 个元素，也就是 $2$ 、 $4$ 、 $5$ 。

这样，我们就可以通过动态规划的方式来解决这道题。

2. 定义状态

定义当前数组 $nums2$ 中元素选择状态为 $state$ ， $state$ 对应选择的元素个数为 $count(state)$ 。

则可以定义状态 $dp[state]$ 表示为：当前数组 $nums2$ 中元素选择状态为 $state$ ，并且选择了 $nums1$ 中前 $count(state)$ 个元素的情况下，可以组成的最小异或值之和。

3. 状态转移方程

对于当前状态 $dp[state]$ ，肯定是从比 $state$ 少选一个元素的状态中递推而来。我们可以枚举少选一个元素的状态，找到可以组成的异或值之和最小值，赋值给 $dp[state]$ 。

举个例子 $nums2 = \lbrace 1, 2, 3, 4 \rbrace$ ， $state = (1001)_2$ ，表示选择了第 $1$ 个元素和第 $4$ 个元素，也就是 $1$ 、 $4$ 。那么 $state$ 只能从 $(1000)_2$ 和 $(0001)_2$ 这两个状态转移而来，我们只需要枚举这两种状态，并求出转移过来的异或值之和最小值。

即状态转移方程为： $dp[state] = min(dp[state], \quad dp[state \oplus (1 \text{ <}\text{< } i)] + (nums1[i] \oplus nums2[one\underline{\hspace{0.5em}}cnt - 1]))$ ，其中 $state$ 第 $i$ 位一定为 $1$ ， $one\underline{\hspace{0.5em}}cnt$ 为 $state$ 中 $1$ 的个数。

4. 初始条件

既然是求最小值，不妨将所有状态初始为最大值。
未选择任何数时，异或值之和为 $0$ ，所以初始化 $dp[0] = 0$ 。

5. 最终结果

根据我们之前定义的状态， $dp[state]$ 表示为：当前数组 $nums2$ 中元素选择状态为 $state$ ，并且选择了 $nums1$ 中前 $count(state)$ 个元素的情况下，可以组成的最小异或值之和。所以最终结果为 $dp[states - 1]$ ，其中 $states = 1 \text{ <}\text{< } n$ 。

思路 1：代码

class Solution:
    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
        ans = float('inf')
        size = len(nums1)
        states = 1 << size

        dp = [float('inf') for _ in range(states)]
        dp[0] = 0
        for state in range(states):
            one_cnt = bin(state).count('1')
            for i in range(size):
                if (state >> i) & 1:
                    dp[state] = min(dp[state], dp[state ^ (1 << i)] + (nums1[i] ^ nums2[one_cnt - 1]))
        
        return dp[states - 1]

思路 1：复杂度分析

时间复杂度： $O(2^n \times n)$ ，其中 $n$ 是数组 $nums1$ 、 $nums2$ 的长度。
空间复杂度： $O(2^n)$ 。

3.2 数组的最大与和

3.2.1 题目链接

2172. 数组的最大与和 - 力扣

3.2.2 题目大意

描述：给定一个长度为 $n$ 的整数数组 $nums$ 和一个整数 $numSlots$ 满足 $2 \times numSlots \ge n$ 。一共有 $numSlots$ 个篮子，编号为 $1 \sim numSlots$ 。

现在需要将所有 $n$ 个整数分到这些篮子中，且每个篮子最多有 $2$ 个整数。

要求：返回将 $nums$ 中所有数放入 $numSlots$ 个篮子中的最大与和。

说明：

与和：当前方案中，每个数与它所在篮子编号的按位与运算结果之和。
- 比如，将数字 $[1, 3]$ 放入篮子 $1$ 中， $[4, 6]$ 放入篮子 $2$ 中，这个方案的与和为 $(1 \text{ AND } 1) + (3 \text{ AND } 1) + (4 \text{ AND } 2) + (6 \text{ AND } 2) = 1 + 1 + 0 + 2 = 4$ 。
$n == nums.length$ 。
$1 \le numSlots \le 9$ 。
$1 \le n \le 2 \times numSlots$ 。
$1 \le nums[i] \le 15$ 。

示例：

示例 1：

输入：nums = [1,2,3,4,5,6], numSlots = 3
输出：9
解释：一个可行的方案是 [1, 4] 放入篮子 1 中，[2, 6] 放入篮子 2 中，[3, 5] 放入篮子 3 中。
最大与和为 (1 AND 1) + (4 AND 1) + (2 AND 2) + (6 AND 2) + (3 AND 3) + (5 AND 3) = 1 + 0 + 2 + 2 + 3 + 1 = 9。

示例 2：

输入：nums = [1,3,10,4,7,1], numSlots = 9
输出：24
解释：一个可行的方案是 [1, 1] 放入篮子 1 中，[3] 放入篮子 3 中，[4] 放入篮子 4 中，[7] 放入篮子 7 中，[10] 放入篮子 9 中。
最大与和为 (1 AND 1) + (1 AND 1) + (3 AND 3) + (4 AND 4) + (7 AND 7) + (10 AND 9) = 1 + 1 + 3 + 4 + 7 + 8 = 24 。
注意，篮子 2 ，5 ，6 和 8 是空的，这是允许的。

3.2.3 解题思路

思路 1：状压 DP

每个篮子最多可分 $2$ 个整数，则我们可以将 $1$ 个篮子分成两个篮子，这样总共有 $2 \times numSlots$ 个篮子，每个篮子中最多可以装 $1$ 个整数。

同时因为 $numSlots$ 的范围为 $[1, 9]$ ， $2 \times numSlots$ 的范围为 $[2, 19]$ ，范围不是很大，所以我们可以用「状态压缩」的方式来表示每个篮子中的整数放取情况。

即使用一个 $n \times numSlots$ 位的二进制数 $state$ 来表示每个篮子中的整数放取情况。如果 $state$ 的第 $i$ 位为 $1$ ，表示第 $i$ 个篮子里边放了整数，如果 $state$ 的第 $i$ 位为 $0$ ，表示第 $i$ 个篮子为空。

这样，我们就可以通过动态规划的方式来解决这道题。

1. 划分阶段

按照 $2 \times numSlots$ 个篮子中的整数放取情况进行阶段划分。

2. 定义状态

定义当前每个篮子中的整数放取情况为 $state$ ， $state$ 对应选择的整数个数为 $count(state)$ 。

则可以定义状态 $dp[state]$ 表示为：将前 $count(state)$ 个整数放到篮子里，并且每个篮子中的整数放取情况为 $state$ 时，可以获得的最大与和。

3. 状态转移方程

对于当前状态 $dp[state]$ ，肯定是从比 $state$ 少选一个元素的状态中递推而来。我们可以枚举少选一个元素的状态，找到可以获得的最大与和，赋值给 $dp[state]$ 。

即状态转移方程为： $dp[state] = min(dp[state], dp[state \oplus (1 \text{ <}\text{< } i)] + (i // 2 + 1) \text{ \& } nums[one\underline{\hspace{0.5em}}cnt - 1])$ ，其中：

$state$ 第 $i$ 位一定为 $1$ 。
$state \oplus (1 \text{ <}\text{< } i)$ 为比 $state$ 少选一个元素的状态。
$i // 2 + 1$ 为篮子对应编号
$nums[one\underline{\hspace{0.5em}}cnt - 1]$ 为当前正在考虑的数组元素。

4. 初始条件

初始每个篮子中都没有放整数的情况下，可以获得的最大与和为 $0$ ，即 $dp[0] = 0$ 。

5. 最终结果

根据我们之前定义的状态， $dp[state]$ 表示为：将前 $count(state)$ 个整数放到篮子里，并且每个篮子中的整数放取情况为 $state$ 时，可以获得的最大与和。所以最终结果为 $max(dp)$ 。

注意：当 $one\underline{\hspace{0.5em}}cnt > len(nums)$ 时，无法通过递推得到 $dp[state]$ ，需要跳过。

思路 1：代码

class Solution:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
        states = 1 << (numSlots * 2)
        dp = [0 for _ in range(states)]

        for state in range(states):
            one_cnt = bin(state).count('1')
            if one_cnt > len(nums):
                continue
            for i in range(numSlots * 2):
                if (state >> i) & 1:
                    dp[state] = max(dp[state], dp[state ^ (1 << i)] + ((i // 2 + 1) & nums[one_cnt - 1]))
        
        return max(dp)

思路 1：复杂度分析

时间复杂度： $O(2^m \times m)$ ，其中 $m = 2 \times numSlots$ 。
空间复杂度： $O(2^m)$ 。