状态压缩 DP 与树形 DP：从空间优化到树状结构的动态规划

状态压缩 DP 与树形 DP从空间优化到树状结构的动态规划一、DP 的空间焦虑与树形困境两种进阶场景的挑战动态规划的基础题型背包、子序列、路径大多可以用二维数组解决状态转移清晰直观。但两类进阶场景会打破这种舒适感一是状态维度爆炸——旅行商问题TSP的朴素 DP 需要 O(n²·2ⁿ) 空间n20 时就需要约 200MB二是树形依赖——树上的 DP 没有天然的线性顺序子树之间的状态传递需要后序遍历且经常面临选/不选当前节点的决策。状态压缩 DP 用二进制位表示集合状态将指数级的集合枚举压缩为整数运算树形 DP 利用树的后序遍历顺序自底向上传递子树状态。两者虽然场景不同但核心思想一致找到状态的紧凑表示方式让转移方程可计算。二、状态压缩 DP 与树形 DP 的原理graph TB subgraph 状态压缩DP A[集合 S 用二进制表示br/S1011 表示选了0,1,3号城市] A -- B[状态转移br/dp S,j min dp S-2^j, i dist i,j] B -- C[遍历顺序br/按 S 的二进制中1的个数递增] end subgraph 树形DP D[后序遍历br/先处理子树] -- E[状态定义br/dp u,0 不选ubr/dp u,1 选u] E -- F[转移方程br/dp u,0 max dp c,0, dp c,1br/dp u,1 dp c,0] end状态压缩 DP 的关键洞察是n 个元素的子集可以用 n 位二进制数表示。枚举所有子集等价于枚举 0 到 2ⁿ-1 的整数。状态转移时通过位运算检查某位是否为 1、设置/清除某位高效操作集合。树形 DP 的关键洞察是树的后序遍历保证了处理当前节点时所有子树的状态已经计算完毕。因此树形 DP 的转移方程天然是自底向上的不需要额外的拓扑排序。三、代码实现3.1 状态压缩 DP旅行商问题from typing import List def tsp(dist: List[List[int]]) - int: 旅行商问题求经过所有城市恰好一次并回到起点的最短路径。 使用状态压缩 DP时间 O(n²·2ⁿ)空间 O(n·2ⁿ)。 n len(dist) if n 1: return 0 INF float(inf) # dp[S][j] 表示已访问集合 S当前在城市 j 的最短路径 # S 用二进制表示第 i 位为 1 表示城市 i 已访问 full_mask (1 n) - 1 dp [[INF] * n for _ in range(1 n)] # 起点为城市 0初始状态只访问了城市 0 dp[1][0] 0 # 按 S 中 1 的个数递增遍历 for s in range(1, 1 n): for u in range(n): if dp[s][u] INF: continue if not (s (1 u)): continue # u 不在集合 S 中跳过 # 尝试从 u 走到未访问的城市 v for v in range(n): if s (1 v): continue # v 已访问跳过 new_state s | (1 v) new_dist dp[s][u] dist[u][v] if new_dist dp[new_state][v]: dp[new_state][v] new_dist # 所有城市都访问后回到起点 0 result INF for u in range(1, n): if dp[full_mask][u] dist[u][0] result: result dp[full_mask][u] dist[u][0] return result3.2 树形 DP树的最大独立集from collections import defaultdict from typing import Dict, List, Tuple class TreeDP: 树形 DP求解树上的最大独立集 def __init__(self, n: int): self.n n self.adj defaultdict(list) def add_edge(self, u: int, v: int) - None: 添加无向边 self.adj[u].append(v) self.adj[v].append(u) def max_independent_set(self) - Tuple[int, List[int]]: 求树的最大独立集。 dp[u][0] 不选节点 u 时以 u 为根的子树的最大独立集 dp[u][1] 选节点 u 时以 u 为根的子树的最大独立集 # dp[u][0]: 不选 u子节点可选可不选 # dp[u][1]: 选 u子节点必须不选 dp [[0, 0] for _ in range(self.n)] visited [False] * self.n def dfs(u: int) - None: visited[u] True dp[u][0] 0 # 不选 u dp[u][1] 1 # 选 u权重为 1 for v in self.adj[u]: if visited[v]: continue # 跳过父节点 dfs(v) # 不选 u 时子节点选或不选取较大值 dp[u][0] max(dp[v][0], dp[v][1]) # 选 u 时子节点必须不选 dp[u][1] dp[v][0] dfs(0) # 回溯求具体方案 selected [] max_size max(dp[0][0], dp[0][1]) def backtrack(u: int, parent_selected: bool) - None: if parent_selected: # 父节点已选当前节点不能选 for v in self.adj[u]: if not visited[v] or v in selected: continue backtrack(v, False) else: # 父节点未选当前节点可选可不选 select_u dp[u][1] dp[u][0] if select_u: selected.append(u) for v in self.adj[u]: if v in selected: continue backtrack(v, select_u) # 简化重新标记 visited 用于回溯 visited [False] * self.n selected [] self._backtrack_simple(0, -1, dp, selected) return max_size, selected def _backtrack_simple( self, u: int, parent: int, dp: List[List[int]], selected: List[int] ) - None: 回溯求最大独立集的具体节点 # 判断是否选择当前节点 if parent -1 or u not in [ v for v in self.adj[parent] ]: # 根节点或非子节点独立判断 pass select_u (parent -1 and dp[u][1] dp[u][0]) or \ (parent ! -1 and dp[u][1] dp[u][0]) # 如果父节点未选且选 u 更优则选 u if parent ! -1: # 检查父节点是否被选 parent_selected parent in selected if not parent_selected and dp[u][1] dp[u][0]: selected.append(u) select_u True else: select_u False else: if dp[u][1] dp[u][0]: selected.append(u) select_u True for v in self.adj[u]: if v ! parent: self._backtrack_simple(v, u, dp, selected)3.3 状态压缩 DP位运算技巧class BitTricks: 状态压缩 DP 中常用的位运算技巧 staticmethod def count_bits(x: int) - int: 统计二进制中 1 的个数集合大小 count 0 while x: x x - 1 # 清除最低位的 1 count 1 return count staticmethod def enumerate_subsets(s: int): 枚举集合 S 的所有非空子集 sub s while sub: yield sub sub (sub - 1) s staticmethod def lowest_bit(x: int) - int: 获取最低位的 1提取最小元素 return x (-x) staticmethod def is_subset(s: int, t: int) - bool: 判断 S 是否为 T 的子集 return (s t) s staticmethod def iterate_by_popcount(n: int): 按 1 的个数递增枚举所有子集 from collections import defaultdict buckets defaultdict(list) for s in range(1 n): cnt bin(s).count(1) buckets[cnt].append(s) for cnt in sorted(buckets.keys()): yield from buckets[cnt]四、状态压缩 DP 与树形 DP 的 Trade-offs 分析状态压缩 DP 的规模限制n20 时2²⁰ ≈ 100 万个状态内存和时间都可接受n25 时2²⁵ ≈ 3300 万开始吃力n30 时2³⁰ ≈ 10 亿不可行。状态压缩 DP 的适用边界是 n ≤ 20-25。超过这个范围需要考虑分支限界、近似算法或问题特化。树形 DP 的树结构依赖树形 DP 要求输入必须是树无环连通图。如果输入是森林多棵树需要对每棵树分别求解再合并如果输入是 DAG需要拓扑排序后再 DP如果输入有环需要先破环如基环树 DP。空间优化状态压缩 DP 的空间为 O(n·2ⁿ)当 n 较大时内存紧张。可以按层滚动只保留当前层和上一层将空间降为 O(2ⁿ)。树形 DP 的空间为 O(n)通常不是瓶颈。回溯求方案DP 求最优值容易但回溯求具体方案需要额外记录转移路径。状态压缩 DP 的回溯需要 O(n·2ⁿ) 的额外空间树形 DP 的回溯可以在 DFS 中同步完成无需额外空间。五、总结状态压缩 DP 和树形 DP 是动态规划的两类进阶范式。状态压缩 DP 用二进制位表示集合将指数级枚举转化为可计算的整数运算适用于 n ≤ 20 的组合优化问题树形 DP 利用后序遍历的自底向上特性在树结构上高效传递状态适用于树上的决策问题。落地建议遇到从 n 个元素中选子集的问题优先考虑状态压缩 DP遇到树上的选/不选决策问题优先考虑树形 DP。两者都需要先定义清晰的状态表示和转移方程再考虑优化。状态压缩 DP 注意规模限制树形 DP 注意输入是否为树。