当前位置：首页 > news >正文

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

news 2026/6/10 23:37:02

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

一、DP 的"空间焦虑"与"树形困境"：两种进阶场景的挑战

动态规划的基础题型（背包、子序列、路径）大多可以用二维数组解决，状态转移清晰直观。但两类进阶场景会打破这种舒适感：一是状态维度爆炸——旅行商问题（TSP）的朴素 DP 需要 O(n²·2ⁿ) 空间，n=20 时就需要约 200MB；二是树形依赖——树上的 DP 没有天然的线性顺序，子树之间的状态传递需要后序遍历，且经常面临"选/不选当前节点"的决策。

状态压缩 DP 用二进制位表示集合状态，将指数级的集合枚举压缩为整数运算；树形 DP 利用树的后序遍历顺序，自底向上传递子树状态。两者虽然场景不同，但核心思想一致：找到状态的紧凑表示方式，让转移方程可计算。

二、状态压缩 DP 与树形 DP 的原理

graph TB subgraph 状态压缩DP A[集合 S 用二进制表示<br/>S=1011 表示选了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 = 不选u<br/>dp u,1 = 选u] E --> F[转移方程<br/>dp u,0 += max dp c,0, dp c,1<br/>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 result

3.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]