状态压缩 DP：简称为「状压 DP」，是一种应用在「小规模数据」的数组 / 字符串上，结合「二进制」的性质来进行状态定义与状态转移的动态规划方法。
我们曾在「位运算知识」章节中，学习过「二进制枚举子集算法」。这里先来回顾一下如何通过二进制枚举子集。
对于一个元素个数为
那么我们就可以用一个长度为
举个例子，比如长度为
比如二进制数
| 集合 S 中元素位置 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|
| 二进位对应值 | 1 | 1 | 1 | 1 | 1 |
| 对应选取状态 | 选取 | 选取 | 选取 | 选取 | 选取 |
再比如二进制数
| 集合 S 中元素位置 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|
| 二进位对应值 | 1 | 0 | 1 | 0 | 1 |
| 对应选取状态 | 选取 | 未选取 | 选取 | 未选取 | 选取 |
再比如二进制数
| 集合 S 中元素位置 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|
| 二进位对应值 | 0 | 1 | 0 | 0 | 1 |
| 对应选取状态 | 未选取 | 选取 | 未选取 | 未选取 | 选取 |
通过上面的例子我们可以得到启发：对于长度为
我们将上面的例子拓展到长度为
- 对于长度为
$n$ 的集合$S$ 来说，只需要枚举$0 \sim 2^n - 1$ （共$2^n$ 种情况），即可得到集合$S$ 的所有子集。
在状压 DP 中，我们通常采用二进制数的形式来表示一维状态，即集合中每个元素的选取情况。
和「二进制枚举子集算法」一样，我们通过一个「
二进制数的每一个二进位都对应了集合中某一个元素的选取状态。如果该二进制数的第
一般来说，状压 DP 的状态转移方式有两种：
- 枚举子集：对于一个状态，枚举它的所有子集，或者枚举所有元素位置，找到比当前状态少选一个元素的子集。然后根据子集的值和状态之间的关系，更新当前状态的值。
- 枚举超集：对于一个状态，枚举它的所有超集。然后根据超集的值和状态之间的关系，更新当前状态的值。
其中，最常用的是「枚举子集」的方式。
对于元素个数不超过
在状压 DP 中，一维状态是集合，对状态进行操作或者状态之间进行转移，也就是要对集合进行操作。
因为我们使用二进制数来定义集合状态，所以对集合进行操作，就是对二进制数进行位运算操作。
如下所示，其中
-
总状态数量：
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，则表示集合中选取了该元素 ...
描述：给定两个整数数组
要求：将
说明：
-
两个数组的异或值之和：$(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。由于数组
同时因为两个数组长度
「状态压缩」指的是使用一个
如果二进制数
举个例子：
-
$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$。
这样，我们就可以通过动态规划的方式来解决这道题。
按照数组
定义当前数组
则可以定义状态
对于当前状态
举个例子
即状态转移方程为：$dp[state] = min(dp[state], \quad dp[state \oplus (1 \text{ <}\text{< } i)] + (nums1[i] \oplus nums2[one\underline{}cnt - 1]))$，其中
- 既然是求最小值，不妨将所有状态初始为最大值。
- 未选择任何数时，异或值之和为
$0$ ，所以初始化$dp[0] = 0$ 。
根据我们之前定义的状态，$dp[state]$ 表示为：当前数组
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]-
时间复杂度：$O(2^n \times n)$，其中
$n$ 是数组$nums1$ 、$nums2$ 的长度。 - 空间复杂度：$O(2^n)$。
描述：给定一个长度为
现在需要将所有
要求：返回将
说明：
-
与和：当前方案中，每个数与它所在篮子编号的按位与运算结果之和。
- 比如，将数字
$[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 是空的，这是允许的。每个篮子最多可分
同时因为
即使用一个
这样，我们就可以通过动态规划的方式来解决这道题。
按照
定义当前每个篮子中的整数放取情况为
则可以定义状态
对于当前状态
即状态转移方程为：$dp[state] = min(dp[state], dp[state \oplus (1 \text{ <}\text{< } i)] + (i // 2 + 1) \text{ & } nums[one\underline{}cnt - 1])$，其中：
-
$state$ 第$i$ 位一定为$1$ 。 -
$state \oplus (1 \text{ <}\text{< } i)$ 为比$state$ 少选一个元素的状态。 -
$i // 2 + 1$ 为篮子对应编号 -
$nums[one\underline{}cnt - 1]$ 为当前正在考虑的数组元素。
- 初始每个篮子中都没有放整数的情况下，可以获得的最大与和为
$0$ ，即$dp[0] = 0$ 。
根据我们之前定义的状态，$dp[state]$ 表示为：将前
注意：当
$one\underline{}cnt > len(nums)$ 时，无法通过递推得到$dp[state]$ ，需要跳过。
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)-
时间复杂度：$O(2^m \times m)$，其中
$m = 2 \times numSlots$ 。 - 空间复杂度：$O(2^m)$。