8.13 状态压缩 DP

---

1. 状态压缩动态规划简介

状态压缩动态规划（状压 DP）：是一种适用于「小规模数据」的数组或字符串问题的动态规划方法。它利用二进制的特性，将集合的选取状态压缩为一个整数，通过位运算实现高效的状态表示与转移。

在「位运算知识」章节中，我们已经学习过「二进制枚举子集」的方法。这里先简要回顾其核心思想。

1.1 二进制枚举子集

对于一个包含 $n$ 个元素的集合 $S$，每个元素都有「选」或「不选」两种状态。我们可以用一个 $n$ 位的二进制数来表示集合 $S$ 的一个子集：第 $i$ 位为 $1$ 表示选取第 $i$ 个元素，为 $0$ 表示不选。

举例说明，设 $S = \lbrace 5, 4, 3, 2, 1 \rbrace$，用 $5$ 位二进制数表示其子集：

• $11111_{(2)}$ 表示选取所有元素，即 $S$ 本身：

元素位置	5	4	3	2	1
选取状态	选取	选取	选取	选取	选取
二进制位	1	1	1	1	1

• $10101_{(2)}$ 表示选取第 $1$、$3$、$5$ 位元素，即 $\lbrace 5, 3, 1 \rbrace$：

元素位置	5	4	3	2	1
选取状态	选取	未选取	选取	未选取	选取
二进制位	1	0	1	0	1

• $01001_{(2)}$ 表示选取第 $1$、$4$ 位元素，即 $\lbrace 4, 1 \rbrace$：

元素位置	5	4	3	2	1
选取状态	未选取	选取	未选取	未选取	选取
二进制位	0	1	0	0	1

由此可见，对于长度为 $n$ 的集合 $S$，只需枚举 $0$ 到 $2^n-1$ 之间的所有整数（共 $2^n$ 种情况），即可遍历 $S$ 的所有子集。

综上所述：

• 长度为 $n$ 的集合 $S$ 的所有子集，可以通过枚举 $0 \sim 2^n-1$ 的二进制数来表示，每一位代表对应元素的选取状态。

1.2 状态定义与状态转移

1.2.1 状态定义

在状态压缩 DP 中，通常用一个二进制数来表示集合中每个元素的选取状态。对于 $n$ 个元素的集合，可以用一个 $n$ 位的二进制数 $state$，其中第 $i$ 位为 $1$ 表示第 $i$ 个元素被选中，为 $0$ 表示未被选中。

这种表示方法与「二进制枚举子集」类似，每一位都精确对应集合中某个元素的选择情况。通过这种方式，可以高效地描述和操作所有可能的选取状态。

1.2.2 状态转移

状态压缩 DP 的状态转移主要有两种常见方式：

1. 枚举子集：对于当前状态，枚举其所有子集，或通过枚举每个元素，找到去掉某个元素后的子状态。根据子状态的值和当前状态的关系，更新当前状态的最优解。
2. 枚举超集：对于当前状态，枚举其所有超集。根据超集的值和当前状态的关系，更新当前状态的最优解。

实际应用中，「枚举子集」是最常用的状态转移方式。

1.3 状压 DP 的适用范围

对于包含 $n$ 个元素的集合，其所有子集的状态总数为 $2^n$，状态数量随 $n$ 呈指数级增长。因此，状态压缩 DP 仅适用于 $n$ 较小的场景（一般 $n \leq 20$）。当 $n$ 较大时，状态数过多，算法效率难以保证，容易超时。

2. 状态压缩 DP 常用位运算技巧

在状态压缩 DP（状压 DP）中，通常用一个整数的二进制位来表示集合的选取状态。对集合的各种操作，本质上就是对二进制数的位运算。下面总结了常用的位运算技巧，设 $n$ 为集合元素个数，$A$、$B$ 为集合对应的二进制状态，$i$ 表示第 $i$ 个元素的位置（从 $0$ 开始）：

• 总状态数：1 << n（即 $2^n$，所有子集的数量）

• 加入第 $i$ 个元素：A = A | (1 << i)（将第 $i$ 位设为 $1$）

• 删除第 $i$ 个元素：A = A & ~(1 << i)（将第 $i$ 位设为 $0$）

• 判断是否选中第 $i$ 个元素：if A & (1 << i): 或 if (A >> i) & 1:

• 置空集：A = 0

• 置全集：A = (1 << n) - 1

• 求补集：A = A ^ ((1 << n) - 1)

• 并集：A | B

• 交集：A & B

• 枚举集合 $A$ 的所有子集（包含 $A$ 本身）：

  subA = A
  while subA:
      ...
      subA = (subA - 1) & A  # 枚举下一个子集
  # 注意：如果需要包含空集，可以在循环后补充 subA = 0 的情况。

• 枚举全集的所有子集：

  for state in range(1 << n):  # state 表示当前子集
      for i in range(n):       # 枚举每一位
          if (state >> i) & 1: # 第 i 位为 1，表示选中了第 i 个元素
              ...

3. 状态压缩 DP 的应用

3.1 经典例题：两个数组最小的异或值之和

3.1.1 题目链接

• 1879. 两个数组最小的异或值之和 - 力扣

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$ 的每个元素选择 $nums2$ 中尚未被选过的元素，使得异或值之和最小。

考虑到 $n$ 的范围较小（$1 \leq n \leq 14$），我们可以用「状态压缩」来表示 $nums2$ 的选取情况。具体做法是用一个 $n$ 位二进制数 $state$，其中第 $i$ 位为 $1$ 表示 $nums2$ 的第 $i$ 个元素已被选中，为 $0$ 表示未被选中。

例如：

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

基于此，我们可以设计动态规划：

1. 阶段划分

以 $nums2$ 的选取状态 $state$ 作为阶段。

2. 定义状态

设 $dp[state]$ 表示当前 $nums2$ 选取状态为 $state$，且已为 $nums1$ 的前 $count(state)$ 个元素分配了数时，能得到的最小异或值之和。其中 $count(state)$ 表示 $state$ 中 $1$ 的个数。

3. 状态转移方程

对于每个 $state$，我们可以枚举 $state$ 中每一个为 $1$ 的位置 $i$，表示最后一个被选的 $nums2[i]$。则 $dp[state]$ 可以由 $dp[state \oplus (1 \ll i)]$ 转移而来，转移代价为 $nums1[count(state)-1] \oplus nums2[i]$。即：

$$dp[state] = \min_{i \text{ 满足 } (state \gg i) \& 1} \left\{ dp[state \oplus (1 \ll i)] + (nums1[count(state)-1] \oplus nums2[i]) \right\}$$

4. 初始条件

• 所有 $dp[state]$ 初始化为无穷大。
• $dp[0] = 0$，即未选任何元素时异或和为 $0$。

5. 最终结果

最终答案为 $dp[states - 1]$，其中 $states = 1 \ll 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 个整数，我们可以将每个篮子拆分为 2 个「格子」，这样总共有 $2 \times numSlots$ 个格子，每个格子最多放 $1$ 个整数。

考虑到 $numSlots$ 的范围为 $[1, 9]$，因此总格子数 $2 \times numSlots$ 也仅为 $[2, 18]$，状态空间较小，适合用二进制压缩表示每个格子的放置情况。

具体地，我们用一个 $2 \times numSlots$ 位的二进制数 $state$ 表示所有格子的放置状态：$state$ 的第 $i$ 位为 $1$ 表示第 $i$ 个格子已放入整数，为 $0$ 表示为空。

基于此，可以设计动态规划求解。

1. 阶段划分

以 $2 \times numSlots$ 个格子的放置状态 $state$ 作为阶段。

2. 定义状态

设 $dp[state]$ 表示：当前已放入 $count(state)$ 个整数，且格子状态为 $state$ 时，能获得的最大与和。

3. 状态转移方程

对于每个状态 $state$，它一定是由某个少放一个整数的状态 $prev = state \text{ \^ } (1 \ll i)$ 转移而来。我们枚举 $state$ 的每一位 $i$，若 $state$ 的第 $i$ 位为 $1$，则可以尝试将第 $count(state)-1$ 个整数放入第 $i$ 个格子，格子编号为 $i // 2 + 1$，对应的与和为 $(i // 2 + 1) \& nums[count(state) - 1]$。状态转移为：

$$dp[state] = \max\left(dp[state],\ dp[state \oplus (1 \ll i)] + ((i // 2 + 1) \& nums[count(state) - 1])\right)$$

其中：

1. $state$ 的第 $i$ 位为 $1$，表示当前格子已放入整数。
2. $state \oplus (1 \ll i)$ 表示去掉第 $i$ 个格子的状态。
3. $i // 2 + 1$ 是该格子对应的篮子编号。
4. $nums[count(state) - 1]$ 是当前要放入的整数。

4. 初始条件

• $dp[0] = 0$，即所有格子为空时，与和为 0。

5. 最终结果

最终答案为所有 $dp[state]$ 中 $count(state) = n$（即所有整数都已放入）的最大值，即 $max(dp)$。

注意：当 $count(state) > len(nums)$ 时，状态无效，应跳过。

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

练习题目

• 1879. 两个数组最小的异或值之和

• 1947. 最大兼容性评分和

• 0526. 优美的排列

• 状态压缩 DP 题目列表