教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载状态压缩动态规划状压 DP是 AlgoNote「算法通关手册」动态规划章节中针对「小规模数据」场景的核心技巧用二进制整数的每一位代表集合中一个元素的「选/不选」再用位运算完成状态转移。本篇将带你从二进制枚举子集出发系统梳理状压 DP 的状态定义、转移范式与常用位运算技巧并结合仓库中两道经典例题1879. 两个数组最小的异或值之和、2172. 数组的最大与和给出可运行的完整代码与复杂度分析最后附上仓库内配套练习清单帮助你快速上手这一类高频面试题型。1. 状态压缩动态规划简介1.1 什么是状态压缩 DP状态压缩动态规划状压 DP是一种适用于「小规模数据」的数组或字符串问题的动态规划方法。它利用二进制的特性将集合的选取状态压缩为一个整数通过位运算实现高效的状态表示与转移。传统的动态规划状态通常是一个或几个维度有限的整数例如下标、容量、剩余步数而当问题中涉及「一个集合中哪些元素被选取」这类组合状态时直接用多维数组表示会非常笨重。状压 DP 的核心思路是用一个整数的二进制位来编码集合的选取情况从而把「集合状态」压缩进一维数组下标配合位运算完成 $O(1)$ 级的查改操作。在 AlgoNote 的课程体系中状压 DP 建立在两个前置知识之上位运算基础位运算章节 介绍了按位与、或、异或、取反、左移、右移六种运算规则以及「判断某数是否为 2 的幂」「计算 1 的个数」等常用技巧二进制枚举子集即本节要回顾的、用 $n$ 位二进制数枚举集合全部子集的方法。1.2 二进制枚举子集回顾对于一个包含 $n$ 个元素的集合 $S$每个元素都有「选」或「不选」两种状态。我们可以用一个 $n$ 位的二进制数来表示集合 $S$ 的一个子集第 $i$ 位为 $1$ 表示选取第 $i$ 个元素为 $0$ 表示不选。举例说明设 $S \lbrace 5, 4, 3, 2, 1 \rbrace$用 $5$ 位二进制数表示其子集$11111_{(2)}$ 表示选取所有元素即 $S$ 本身元素位置54321选取状态选取选取选取选取选取二进制位11111$10101_{(2)}$ 表示选取第 $1$、$3$、$5$ 位元素即 $\lbrace 5, 3, 1 \rbrace$元素位置54321选取状态选取未选取选取未选取选取二进制位10101$01001_{(2)}$ 表示选取第 $1$、$4$ 位元素即 $\lbrace 4, 1 \rbrace$元素位置54321选取状态未选取选取未选取未选取选取二进制位01001由此可见对于长度为 $n$ 的集合 $S$只需枚举 $0$ 到 $2^n-1$ 之间的所有整数共 $2^n$ 种情况即可遍历 $S$ 的所有子集。小结长度为 $n$ 的集合 $S$ 的所有子集可以通过枚举 $0 \sim 2^n-1$ 的二进制数来表示每一位代表对应元素的选取状态。完整的二进制枚举子集代码可参考位运算章节中的subsets实现外层循环for i in range(1 n)枚举 $0 \sim 2^n-1$ 的每种选取方案内层循环if (i j) 1判断第 $j$ 位是否为 $1$ 来决定是否选取元素S[j]。1.3 状态定义与状态转移1.3.1 状态定义在状态压缩 DP 中通常用一个二进制数来表示集合中每个元素的选取状态。对于 $n$ 个元素的集合可以用一个 $n$ 位的二进制数 $state$其中第 $i$ 位为 $1$ 表示第 $i$ 个元素被选中为 $0$ 表示未被选中。这种表示方法与「二进制枚举子集」类似每一位都精确对应集合中某个元素的选择情况。通过这种方式可以高效地描述和操作所有可能的选取状态。在代码实现中dp数组的长度即为1 n下标state直接承载了集合状态。1.3.2 状态转移状态压缩 DP 的状态转移主要有两种常见方式枚举子集对于当前状态枚举其所有子集或通过枚举每个元素找到去掉某个元素后的子状态。根据子状态的值和当前状态的关系更新当前状态的最优解。枚举超集对于当前状态枚举其所有超集。根据超集的值和当前状态的关系更新当前状态的最优解。实际应用中「枚举子集」是最常用的状态转移方式。从 AlgoNote 各题解的实现来看最典型的写法是外层循环从小到大枚举所有state内层循环枚举state中每一个为1的位i通过state ^ (1 i)得到少选一个元素的子状态再与当前状态做min/max/ 累加更新下文两个经典例题都是这一范式的直接体现。1.4 状压 DP 的适用范围对于包含 $n$ 个元素的集合其所有子集的状态总数为 $2^n$状态数量随 $n$ 呈指数级增长。因此状态压缩 DP 仅适用于 $n$ 较小的场景一般 $n \leq 20$。当 $n$ 较大时状态数过多算法效率难以保证容易超时。从仓库中的例题约束也能印证这一点两个数组异或值之和的 $n$ 上限为 $14$状态数约 $1.6$ 万数组最大与和的numSlots上限为 $9$状态数 $2^{18}262144$优美的排列的 $n$ 上限为 $15$状态数 $2^{15}32768$。这些题目之所以能放心使用状压 DP正是因为其数据规模被刻意限制在了 $2^{20}$ 级别以内。2. 状态压缩 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:检查第 $i$ 位是否为 $1$置空集A 0空集对应整数 $0$置全集A (1 n) - 1所有位均为 $1$求补集A A ^ ((1 n) - 1)与全集异或翻转全部位并集A | B按位或交集A B按位与枚举集合 $A$ 的所有子集包含 $A$ 本身见下方代码从 $A$ 出发递减掩码枚举全集的所有子集见下方代码遍历 $0 \sim 2^n-1$枚举集合 $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 个元素 ...这些位运算技巧是整个状压 DP 的「积木」。此外在仓库题解中还频繁用到两个统计操作值得单独说明统计状态中 1 的个数bin(state).count(1)Python 内置方法用于确定当前状态已经选取了多少个元素即 $count(state)$统计最低位 1 的个数替代方案利用n (n - 1)循环清零最低位详见位运算章节中「计算二进制中二进位为 1 的个数」一节的hammingWeight实现。3. 状态压缩 DP 的应用下面进入实战环节以原文档中的两道经典例题为主线结合仓库内对应题解文件展开完整推导。两道题分别代表状压 DP 的「最小值」与「最大值」两个方向。3.1 经典例题两个数组最小的异或值之和3.1.1 题目链接1879. 两个数组最小的异或值之和 - 力扣仓库配套题解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) 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 解题思路状态压缩 DP由于 $nums2$ 可以任意重排我们可以固定 $nums1$ 的顺序依次为 $nums1$ 的每个元素选择 $nums2$ 中尚未被选过的元素使得异或值之和最小。考虑到 $n$ 的范围较小$1 \leq n \leq 14$我们可以用「状态压缩」来表示 $nums2$ 的选取情况。具体做法是用一个 $n$ 位二进制数 $state$其中第 $i$ 位为 $1$ 表示 $nums2$ 的第 $i$ 个元素已被选中为 $0$ 表示未被选中。例如$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. 阶段划分以 $nums2$ 的选取状态 $state$ 作为阶段。状态从小到大枚举保证每个状态在被访问到时其全部「少选一个元素」的子状态均已求解完毕自底向上的递推顺序。2. 定义状态设 $dp[state]$ 表示当前 $nums2$ 选取状态为 $state$且已为 $nums1$ 的前 $count(state)$ 个元素分配了数时能得到的最小异或值之和。其中 $count(state)$ 表示 $state$ 中 $1$ 的个数代码中用bin(state).count(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} $$这里的一个关键细节是下标映射。当状态中已有 $count(state)$ 个元素被选中时意味着当前正在为 $nums1$ 的第 $count(state)-1$ 个元素下标从 0 开始安排配对对象因此转移代价中的nums1下标取count(state)-1而nums2的下标则是本轮枚举到的、状态中为 1 的那个位i。这与仓库题解中的代码实现完全对应。4. 初始条件所有 $dp[state]$ 初始化为无穷大float(inf)因为求解目标是最小值。$dp[0] 0$即未选任何元素时异或和为 $0$。5. 最终结果最终答案为 $dp[states - 1]$其中 $states 1 \ll n$即所有元素都被选中的状态。3.1.4 完整代码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]说明代码与仓库题解中的实现一致其中dp[state ^ (1 i)]即「去掉第 $i$ 个元素后的子状态」nums2[one_cnt - 1]对应「当前要配对给第 $one_cnt-1$ 个 $nums1$ 元素的 $nums2$ 值」——注意这一版代码实际上利用了nums1固定顺序、逐个配对的对称性异或运算的交换律保证配对关系等价。实际实现中下标写法的微调不影响正确性核心仍是「状态压缩 枚举子状态转移」。3.1.5 复杂度分析时间复杂度$O(2^n \times n)$其中 $n$ 是数组 $nums1$、$nums2$ 的长度。外层遍历 $2^n$ 个状态内层最多枚举 $n$ 个位。空间复杂度$O(2^n)$。需要一维dp数组保存 $2^n$ 个状态值。3.2 经典例题数组的最大与和3.2.1 题目链接2172. 数组的最大与和 - 力扣仓库配套题解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 解题思路状态压缩 DP由于每个篮子最多能放 2 个整数我们可以将每个篮子拆分为 2 个「格子」这样总共有 $2 \times numSlots$ 个格子每个格子最多放 $1$ 个整数。考虑到 $numSlots$ 的范围为 $[1, 9]$因此总格子数 $2 \times numSlots$ 也仅为 $[2, 18]$状态空间较小$2^{18}262144$适合用二进制压缩表示每个格子的放置情况。具体地我们用一个 $2 \times numSlots$ 位的二进制数 $state$ 表示所有格子的放置状态$state$ 的第 $i$ 位为 $1$ 表示第 $i$ 个格子已放入整数为 $0$ 表示为空。基于此可以设计动态规划求解。1. 阶段划分以 $2 \times numSlots$ 个格子的放置状态 $state$ 作为阶段同样按状态从小到大递推。2. 定义状态设 $dp[state]$ 表示当前已放入 $count(state)$ 个整数且格子状态为 $state$ 时能获得的最大与和。3. 状态转移方程对于每个状态 $state$它一定是由某个少放一个整数的状态 $prev state \oplus (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) $$其中$state$ 的第 $i$ 位为 $1$表示当前格子已放入整数。$state \oplus (1 \ll i)$ 表示去掉第 $i$ 个格子的状态。$i // 2 1$ 是该格子对应的篮子编号整除向下取整格子和篮子按 $0$、$1$ 一组划分。$nums[count(state) - 1]$ 是当前要放入的整数。4. 初始条件$dp[0] 0$即所有格子为空时与和为 0。5. 最终结果最终答案为所有 $dp[state]$ 中 $count(state) n$即所有整数都已放入的最大值即 $max(dp)$。注意当 $count(state) len(nums)$ 时状态无效应跳过。因为格子数最多 $2 \times numSlots$可能大于整数个数 $n$此时某些状态会「放不下」对应个数的整数直接continue跳过即可。3.2.4 完整代码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)3.2.5 复杂度分析时间复杂度$O(2^m \times m)$其中 $m 2 \times numSlots$。外层遍历 $2^m$ 个状态内层枚举 $m$ 个格子位。空间复杂度$O(2^m)$。一维dp数组大小为 $2^m$。3.3 两题对比状压 DP 的通用套路把上面两道题放在一起对比可以提炼出状压 DP 的通用五步法步骤1879 异或值之和最小值2172 最大与和最大值状态表示$n$ 位二进制表示 $nums2$ 的选取情况$2\times numSlots$ 位二进制表示格子放置情况状态定义$dp[state]$前 $count(state)$ 个元素配对的最小异或和$dp[state]$已放 $count(state)$ 个整数时的最大与和阶段划分按 $state$ 从小到大按 $state$ 从小到大转移方向枚举 $state$ 中为 1 的位state ^ (1 i)为子状态同左更新方式minmax初始化$dp[0]0$其余inf$dp[0]0$其余0答案$dp[states-1]$max(dp)仅统计 $count(state)n$可以看到状压 DP 的骨架高度一致压缩状态 → 统计 1 的个数确定阶段 → 枚举子状态做转移。区别只在于状态编码的位数、转移代价的计算式与聚合函数min/max/ 累加。掌握这套骨架后优美的排列 这类「计数」型题目状态定义 $dp[state]$ 为方案数转移为累加也能轻松套用。4. 练习题目与延伸阅读4.1 配套练习1879. 两个数组最小的异或值之和1947. 最大兼容性评分和中等学生-导师配对的最大化状态压缩 预计算评分矩阵0526. 优美的排列中等计数型状压 DP题解同时给出了回溯、二维状压 DP 与一维优化三种思路4.2 仓库中的更多状压 DP 题目在题目分类列表的「状态压缩 DP 题目」一节中还收录了数十道进阶题目例如1595. 连通两组点的最小成本困难1349. 参加考试的最大学生数困难矩阵上的行间状态压缩0643. 大礼包Shopping Offers中等状态压缩 记忆化搜索0698. 划分为 k 个相等的子集中等回溯与状压的结合0847. 访问所有节点的最短路径困难状压 BFS1986. 完成任务的最少工作时间段中等建议的学习路径是先吃透本节两道例题的「最小/最大」两个方向再用优美的排列体会「计数」方向和一维状态优化最后通过上表中的进阶题巩固对不同编码方式行状态、图访问状态、背包分配状态的建模能力。4.3 与其他动态规划章节的衔接状压 DP 在 AlgoNote 动态规划体系中属于「进阶技巧」建议按如下顺序学习先掌握动态规划基础中的三特征最优子结构、重叠子问题、无后效性与五步法阶段划分、定义状态、状态转移、初始条件、最终结果再了解记忆化搜索自顶向下实现方式可与状压结合例如大礼包一题最后学习本节的状态压缩 DP并可与位运算基础配合复习位运算技巧。状压 DP 的「状态」天然满足无后效性每个二进制状态一旦确定就不再改变后续决策只影响之后的状态这与动态规划基础章节中强调的「无后效性」原则完全吻合也是它能够直接套用自底向上递推的根本原因。5. 总结状压 DP 用二进制整数编码集合选取状态把指数级组合状态压缩进一维dp数组下标配合位运算实现高效转移其适用前提是数据规模小一般 $n \leq 20$状态总数 $2^n$ 可控状态转移以「枚举子集 / 枚举子状态」为主流范式枚举state中为 1 的位用state ^ (1 i)取得子状态常用位运算包括1 n总状态数、A | (1 i)加入元素、A ~(1 i)删除元素、(A i) 1判断选取、(subA - 1) A枚举子集以及bin(state).count(1)统计已选元素个数通过「最小异或值之和min」与「最大与和max」两道经典题可以完整掌握从状态编码、状态定义到转移与初始化的全套建模流程。掌握状压 DP相当于掌握了处理「小规模集合最优化/计数」问题的通用武器。在 AlgoNote 中继续刷完状态压缩 DP 题目列表中的练习即可在面试中从容应对这类高频题型。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐FreeCAD免费3D参数化建模完全指南从第一个零件到结构分析一次学会FreeCAD免费3D参数化建模完全指南从第一个零件到结构分析一次学会 FreeCAD 是一款完全免费、开源的跨平台 3D 参数化建模软件面向机械工程师、桌面应用3D建模图形学工业制造doocs/leetcode 状态压缩DP位运算在动态规划中的巧妙应用doocs/leetcode 状态压缩DP位运算在动态规划中的巧妙应用 引言当状态数量爆炸时 在算法竞赛和面试中动态规划Dynamic Programm示例工程教程把摄像头变成 AI 哨兵Frigate 本地实时物体检测不依赖云把摄像头变成 AI 哨兵Frigate 本地实时物体检测不依赖云 回看录像靠人肉拖时间轴Frigate 把录像变成事件索引 家里装的摄像头一天 2人工智能计算机视觉音视频上一篇VimWiki style.css深度解析6个技巧快速定制个人Wiki网站样式完整指南下一篇ncmdump三步解锁网易云NCM加密音乐重获你的数字音乐自由创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考