状态压缩 DP 的实现技巧位运算不是炫技是省空间一、n20 时的指数空间问题典型的状压 DP 题目如 TSP 旅行商问题的状态空间是 O(n × 2^n)。当 n20 时2^20 1,048,576 个状态每个状态用整数表示空间约为 8 MB完全可以接受。但当 n24 时2^24 16,777,216空间膨胀到 128 MB 以上需要精打细算。状态压缩 DP 的精髓不是「用二进制表示状态」而是用位运算在整数中紧凑编码同时保证状态转移的高效性。二、位运算的核心操作flowchart LR A[状态 mask: 整数] -- B[基本操作] B -- B1[检查第 i 位: mask 1 i] B -- B2[设置第 i 位: mask | 1 i] B -- B3[清除第 i 位: mask ~ 1 i] B -- B4[翻转第 i 位: mask ^ 1 i] B -- B5[最低位的 1: mask -mask] A -- C[高阶操作] C -- C1[子集枚举: sub sub-1 mask] C -- C2[统计 1 的个数: popcount] C -- C3[遍历所有 1 的位置]三、工程化实现from typing import List class BitmaskUtils: 位运算工具集常用操作的高效实现 每个操作都有对应的时间复杂度说明。 staticmethod def has_bit(mask: int, i: int) - bool: 判断 mask 的第 i 位是否为 1O(1) return (mask i) 1 1 staticmethod def set_bit(mask: int, i: int) - int: 将 mask 的第 i 位置为 1O(1) return mask | (1 i) staticmethod def clear_bit(mask: int, i: int) - int: 将 mask 的第 i 位置为 0O(1) return mask ~(1 i) staticmethod def toggle_bit(mask: int, i: int) - int: 翻转 mask 的第 i 位O(1) return mask ^ (1 i) staticmethod def lowest_set_bit(mask: int) - int: 获取 mask 最低位的 1值为 2^k非位置索引O(1) return mask -mask staticmethod def popcount(mask: int) - int: 统计 mask 中 1 的个数O(1)Python 3.8 内置 return mask.bit_count() staticmethod def iterate_set_bits(mask: int): 遍历 mask 中所有为 1 的位O(k)k 为 1 的个数 与直接 for i in range(n) 不同这个遍历只访问为 1 的位。 在稀疏 mask 中效率高得多。 while mask: lsb mask -mask # lsb 的位置 (lsb.bit_length() - 1) yield lsb.bit_length() - 1 mask ^ lsb staticmethod def enumerate_subsets(mask: int): 枚举 mask 的所有子集包括空集O(3^n → 实际 O(2^k)) sub mask while True: yield sub if sub 0: break # 关键技巧每次减 1 后与 mask 取交 # 确保 sub 始终是 mask 的子集 sub (sub - 1) mask staticmethod def enumerate_subsets_of_size(mask: int, k: int): 枚举 mask 的所有大小为 k 的子集 # Gospers Hack生成下一个相同 popcount 的整数 sub (1 k) - 1 while sub mask: if (sub mask) sub: yield sub # Gospers Hack 的核心公式 if sub 0: break c sub -sub r sub c sub (((r ^ sub) 2) // c) | r # ---- 经典状压 DPTSP 旅行商问题 ---- def tsp_shortest_path(dist: List[List[int]]) - int: 旅行商问题状态压缩 DP 解法 状态定义dp[mask][i] 已访问 mask 中的城市当前在城市 i 的最短路径 状态转移dp[mask | (1j)][j] min(dp[mask][i] dist[i][j]) 空间优化技巧 1. 使用一维 DP 滚动数组省略城市维度 2. 只存储可达的状态 n len(dist) INF float(inf) # 使用字典而非二维数组只存储有意义的 mask # 在 n20 时所有 mask 都有意义数组更优 # 在 n24 时字典只存储已访问的状态节省了不可达状态的空间 dp {} # 起点只访问了城市 0当前在城市 0 dp[(1, 0)] 0 # 按访问城市数递增递推自底向上 for visited_count in range(1, n): new_dp {} for (mask, last), cost in dp.items(): for nxt in range(n): if mask (1 nxt): continue # 已访问过 new_mask mask | (1 nxt) new_cost cost dist[last][nxt] key (new_mask, nxt) if key not in new_dp or new_cost new_dp[key]: new_dp[key] new_cost dp new_dp # 回到起点 full_mask (1 n) - 1 ans INF for last in range(1, n): if (full_mask, last) in dp: ans min(ans, dp[(full_mask, last)] dist[last][0]) return ans # ---- 状压 DP分配问题每个人分配一个任务 ---- def assignment_min_cost(cost: List[List[int]]) - int: 分配问题n 个人分配到 n 个任务的最小总成本 状态定义dp[mask] 已分配 mask 中的任务的最小成本 mask 中第 j 位为 1 表示第 j 个任务已分配 时间复杂度O(n × 2^n)空间复杂度O(2^n) n len(cost) # 使用数组存储2^n 个状态 dp [float(inf)] * (1 n) dp[0] 0 for mask in range(1 n): # 已分配的任务数 popcount(mask) i mask.bit_count() if i n: continue # 为第 i 个人分配未分配的任务 for j in range(n): if mask (1 j): continue new_mask mask | (1 j) dp[new_mask] min(dp[new_mask], dp[mask] cost[i][j]) return dp[(1 n) - 1]四、边界与优化技巧4.1 Python 整数的位运算特性Python 的int是任意精度的不像 C 的int限制 32/64 位。这意味着可以处理 n 64 的状压 DP如 n100但1 100的大整数运算开销会增大。实际上 n 超过 30 时状压 DP 应该考虑其他优化如 meet-in-the-middle。4.2bit_count()的性能Python 3.8 的int.bit_count()是 C 实现比手动循环统计快数十倍。在 DP 循环中频繁需要 popcount 时应该使用它。4.3 子集枚举的效率enumerate_subsets的总复杂度是 O(3^n)但实际遍历的子集数量是 Σ C(n,k) × 2^k 3^n。在 n15 时约 1400 万次迭代在 Python 中约需 1-2 秒。如果 n20约 35 亿明显不可行。4.4 字典 vs 数组存储在dp[mask]这种只有一维状态的场景数组永远优于字典。在dp[mask][i]这种二维状态中如果很多 mask 不可达字典可能更优——但字典的 Python 对象开销很大需要实际 profiling 才能确定。五、总结状压 DP 的位运算不是花活是真实的空间优化需求驱动的。当 n 在 15-24 之间时2^n 个状态恰好是内存可接受但需要谨慎处理的量级。理解每个位操作的含义和代价才能在 DP 循环中避免不必要的开销。最重要的是状压 DP 的编码方式是服务于问题模型的——先有模型再有编码而非为了炫技而编码。