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
求集合 $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.1 题目链接

1879. 两个数组最小的异或值之和 - 力扣open in new window

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$ 。

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

1. 划分阶段

按照数组 $nums$ 中元素选择情况进行阶段划分。

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. 数组的最大与和 - 力扣open in new window

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)$ 。

01. 状态压缩 DP 知识

# 状态压缩 DP 知识

# 1. 状态压缩 DP 简介

# 1.1 二进制枚举子集

# 1.2 状态定义与状态转移

# 1.2.1 状态定义

# 1.2.1 状态转移

# 1.3 状压 DP 的使用条件

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

# 3. 状态压缩 DP 的应用

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

# 3.1.1 题目链接

# 3.1.2 题目大意

# 3.1.3 解题思路

# 思路 1：状态压缩 DP

# 1. 划分阶段

# 2. 定义状态

# 3. 状态转移方程

# 4. 初始条件

# 5. 最终结果

# 思路 1：代码

# 思路 1：复杂度分析

# 3.2 数组的最大与和

# 3.2.1 题目链接

# 3.2.2 题目大意

# 3.2.3 解题思路

# 思路 1：状压 DP

# 1. 划分阶段

# 2. 定义状态

# 3. 状态转移方程

# 4. 初始条件

# 5. 最终结果

# 思路 1：代码

# 思路 1：复杂度分析

状态压缩 DP 知识

1. 状态压缩 DP 简介

1.1 二进制枚举子集

1.2 状态定义与状态转移

1.2.1 状态定义

1.2.1 状态转移

1.3 状压 DP 的使用条件

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

3. 状态压缩 DP 的应用

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

3.1.1 题目链接

3.1.2 题目大意

3.1.3 解题思路

思路 1：状态压缩 DP

1. 划分阶段

2. 定义状态

3. 状态转移方程

4. 初始条件

5. 最终结果

思路 1：代码

思路 1：复杂度分析

3.2 数组的最大与和

3.2.1 题目链接

3.2.2 题目大意

3.2.3 解题思路

思路 1：状压 DP

1. 划分阶段

2. 定义状态

3. 状态转移方程

4. 初始条件

5. 最终结果

思路 1：代码

思路 1：复杂度分析