动态规划（三）：树形与状压
第二十九章：动态规划（三）— 树形与状压
前两章我们征服了一维 DP、背包、序列 DP 和区间 DP。这一章进入动态规划的"高级武器库"：当状态空间不再是线性序列或矩形网格，而是树或集合的子集时，我们需要全新的状态表示方式。
树形 DP 的核心思想是自底向上：先算出所有子树的最优解，再合并到父节点。状态压缩 DP 的核心思想是用二进制位表示集合：一个 n 位整数可以编码 2^n 种子集状态，把"哪些元素已被选择"压缩进一个整数。数位 DP 和博弈 DP 则是状态定义的进一步推广。
这些技巧在面试中属于"压轴题"级别——能写出来的候选人凤毛麟角，但原理其实并不神秘。
Level 1 · 你需要知道的
29.1 树形 DP 概念
什么是树形 DP
树形 DP 是指在树结构上进行动态规划。与线性 DP 不同，树的拓扑结构决定了转移的方向：一个节点的状态依赖于其所有子节点的状态。
为什么需要树形 DP？ 因为很多现实问题天然是树状的：组织架构（能不能同时邀请直属上下级参加派对？）、文件系统、编译器的语法树、网络拓扑。在这些结构上求最优解，线性 DP 无法直接套用。
核心范式
def dfs(node):
# 1. 初始化当前节点的状态
# 2. 递归处理每个子节点
for child in node.children:
dfs(child)
# 3. 用子节点的结果更新当前节点的状态
# 4. 返回当前节点的最终状态
这是后序遍历（post-order traversal）的结构——先处理子树，再处理当前节点。
29.2 打家劫舍 III（LeetCode #337）
问题描述
一棵二叉树，每个节点上有一个非负整数代表可偷金额。规则：不能同时偷直接相连的两个节点（即父子不能同时偷）。求能偷到的最大金额。
状态定义
对每个节点，定义两个状态：
rob：偷这个节点时，以该节点为根的子树能获得的最大金额not_rob：不偷这个节点时，以该节点为根的子树能获得的最大金额
转移方程
rob(node) = node.val + not_rob(left) + not_rob(right)
# 偷当前节点，则左右孩子都不能偷
not_rob(node) = max(rob(left), not_rob(left)) + max(rob(right), not_rob(right))
# 不偷当前节点，左右孩子各自独立选择偷或不偷
为什么这样设计状态？ 关键约束是"父子不能同时偷"。如果我们只定义一个状态 dp[node] = 以 node 为根能偷的最大值，在转移时无法区分 node 本身是否被偷——但这个信息对 node 的父节点至关重要。所以必须拆成两个状态。
完整代码
from typing import Optional, Tuple
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rob(root: Optional[TreeNode]) -> int:
"""打家劫舍 III：树形 DP"""
def dfs(node: Optional[TreeNode]) -> Tuple[int, int]:
"""返回 (偷当前节点的最大值, 不偷当前节点的最大值)"""
if not node:
return (0, 0)
left_rob, left_not = dfs(node.left)
right_rob, right_not = dfs(node.right)
# 偷当前节点：左右孩子都不能偷
rob_current = node.val + left_not + right_not
# 不偷当前节点：左右孩子各自取最大
not_rob_current = max(left_rob, left_not) + max(right_rob, right_not)
return (rob_current, not_rob_current)
r, nr = dfs(root)
return max(r, nr)
时间复杂度：O(n)，每个节点访问一次。 空间复杂度：O(h)，h 为树高，递归栈深度。
常见错误
- 忘记返回两个状态：只返回一个最大值，导致父节点无法判断子节点是否被偷
- 重复计算：用记忆化但 key 选择不当（节点对象不可哈希）——直接用后序遍历一次性计算更优雅
- 混淆"不偷"和"一定不偷子树中任何节点"：不偷当前节点不意味着必须偷子节点，子节点也可以不偷
29.3 状态压缩 DP 概念
什么是状压 DP
状态压缩 DP（Bitmask DP）用一个整数的二进制表示来编码集合的选取状态。如果有 n 个元素，每个元素"选/不选"两种状态，总共 2^n 种组合——用一个 n 位二进制数就能完整表示。
为什么需要状压 DP？ 考虑这样的问题：给你 n 个城市，求经过所有城市恰好一次的最短路径（旅行商问题 TSP）。如果用暴力枚举所有排列，复杂度是 O(n!)。但如果我们把"已经访问过哪些城市"压缩为一个位掩码，就能把问题转化为 DP，复杂度降到 O(n^2 * 2^n)——对 n <= 20 的情况完全可行。
位运算基础
# 检查第 i 位是否为 1（第 i 个元素是否在集合中）
(mask >> i) & 1
# 将第 i 位设为 1（把第 i 个元素加入集合）
mask | (1 << i)
# 将第 i 位设为 0（把第 i 个元素从集合中移除）
mask & ~(1 << i)
# 枚举 mask 的所有子集
sub = mask
while sub > 0:
# 处理子集 sub
sub = (sub - 1) & mask
29.4 旅行商问题（TSP）
问题描述
给定 n 个城市和任意两个城市之间的距离矩阵 dist[i][j]，求从城市 0 出发，经过所有城市恰好一次，再回到城市 0 的最短路径长度。
状态定义
dp[mask][i] 表示：已经访问了 mask 所表示的城市集合，当前停在城市 i 时的最短路径长度。
注意：mask 是一个 n 位二进制数，第 k 位为 1 表示城市 k 已被访问。
转移方程
dp[mask][i] = min(dp[mask ^ (1 << i)][j] + dist[j][i])
其中 j 满足：j != i，且 j 在 mask 中（即 mask 的第 j 位为 1）
mask ^ (1 << i) 表示从 mask 中去掉城市 i 后的状态
直觉理解：要到达状态 (mask, i)，必须从某个城市 j 转移过来——j 是 mask 中除了 i 之外的某个城市，从 j 走到 i 花费 dist[j][i]。
初始条件
dp[1][0] = 0 # 只访问了城市 0，当前在城市 0，路径长度为 0
（这里 mask = 1 表示只有第 0 位为 1）
最终答案
answer = min(dp[(1 << n) - 1][i] + dist[i][0]) 对所有 i != 0
# 所有城市都访问了，从最后一个城市回到起点
完整代码
def tsp(dist: list[list[int]]) -> int:
"""
旅行商问题：状压 DP
dist[i][j] 表示城市 i 到城市 j 的距离
返回从城市 0 出发经过所有城市恰好一次再回到城市 0 的最短距离
"""
n = len(dist)
INF = float('inf')
# dp[mask][i]: 已访问 mask 表示的城市集合，当前在城市 i 的最短路径
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0 # 起点：只访问了城市 0
for mask in range(1, 1 << n):
for i in range(n):
if dp[mask][i] == INF:
continue
if not (mask >> i & 1):
continue # 城市 i 不在 mask 中，状态不合法
# 从城市 i 出发，尝试访问尚未访问的城市 j
for j in range(n):
if mask >> j & 1:
continue # 城市 j 已经访问过
new_mask = mask | (1 << j)
dp[new_mask][j] = min(dp[new_mask][j], dp[mask][i] + dist[i][j])
# 所有城市都访问后，回到起点
full_mask = (1 << n) - 1
ans = INF
for i in range(1, n):
if dp[full_mask][i] != INF:
ans = min(ans, dp[full_mask][i] + dist[i][0])
return ans
时间复杂度：O(n^2 * 2^n)。外层枚举所有 2^n 个 mask，内层枚举当前城市 i 和下一个城市 j。
空间复杂度：O(n * 2^n)。
实际限制：n = 20 时，2^20 = 1048576，乘以 n^2 = 400，约 4 亿次操作——用 Python 会超时，C++ 可以在 1-2 秒内完成。面试中 n 通常不超过 15。
Level 2 · 它是怎么运行的
29.5 数位 DP
问题引入：数字 1 的个数（LeetCode #233）
给定整数 n，计算 1 到 n 中所有整数里数字 1 出现的总次数。例如 n = 13，答案是 6（1, 10, 11, 12, 13 中 1 出现了 6 次）。
数位 DP 的核心思想
数位 DP 把数字看成一串数位（digit），从高位到低位逐位决策。核心技巧是维护一个 tight 标记：
tight = True：当前已选的前缀等于 n 对应位置的前缀，后面的位不能超过 n 对应的位tight = False：当前已选的前缀小于 n 对应位置的前缀，后面的位可以随意取 0-9
这个技巧保证我们只统计 [1, n] 范围内的数。
为什么需要 tight 约束？ 假设 n = 345。当我们在百位选了 3，十位就不能超过 4；但如果百位选了 2，十位可以取 0-9 的任何值。tight 标记正是为了区分这两种情况。
通用框架
from functools import lru_cache
def count_digit_one(n: int) -> int:
"""LeetCode 233: 数字 1 的个数"""
if n <= 0:
return 0
digits = list(str(n))
length = len(digits)
@lru_cache(maxsize=None)
def dp(pos: int, count: int, tight: bool, started: bool) -> int:
"""
pos: 当前处理第几位（从高位到低位）
count: 已经出现的 1 的个数
tight: 当前是否受上界约束
started: 是否已经开始填非零数字（处理前导零）
"""
if pos == length:
return count # 所有位都决策完毕，返回 1 的个数
limit = int(digits[pos]) if tight else 9
total = 0
for d in range(0, limit + 1):
new_tight = tight and (d == limit)
new_started = started or (d != 0)
new_count = count + (1 if d == 1 else 0)
total += dp(pos + 1, new_count, new_tight, new_started)
return total
return dp(0, 0, True, False)
逐步执行示例（n = 13）
digits = ['1', '3']
十位（pos=0）:
d=0: tight=False, 进入个位可选 0-9
其中 d=1 贡献 1 次 → 子树贡献 1
d=1: tight=True, 进入个位可选 0-3
十位本身贡献 1
个位 d=0: count=1, 贡献 1
个位 d=1: count=2, 贡献 2（十位的1 + 个位的1）
个位 d=2: count=1, 贡献 1
个位 d=3: count=1, 贡献 1
子树贡献 = 1+2+1+1 = 5
总计 = 1 + 5 = 6 ✓
数位 DP 的通用性
这个框架可以解决大量"统计 [L, R] 范围内满足某种数位条件的数"的问题：
- 不含前导零的数中各位数字之和为 k 的数有多少个
- 相邻两位数字之差不超过 1 的数
- 二进制表示中 1 的个数为质数的数
所有这些问题都套用同一个框架，只需修改状态参数和转移条件。
29.6 博弈类 DP
Nim 游戏
两个玩家轮流从石子堆中取石子，每次至少取 1 个、最多取 3 个，取到最后一个石子的人赢。问先手是否有必胜策略。
关键结论：如果石子数 n % 4 == 0，后手必胜；否则先手必胜。
为什么是 4？ 这是 Sprague-Grundy 理论的一个特例。分析小情况：
- n=1,2,3：先手直接取完，先手胜
- n=4：先手无论取 1/2/3 个，剩下 3/2/1 个给后手，后手胜
- n=5,6,7：先手取 1/2/3 个，给对方留下 4 个，先手胜
- n=8：先手无论怎么取，给对方留下 5/6/7 个，对方可以留 4 给你
规律清晰：n 是 4 的倍数时先手必败，否则先手必胜。
def can_win_nim(n: int) -> bool:
"""Nim 游戏：每次取 1-3 个"""
return n % 4 != 0
石子游戏（LeetCode #877）
两个人轮流从一排石子中取，每次只能取最左边或最右边的一堆。石子总数为奇数，不存在平局。问先手是否一定赢。
状态定义
dp[i][j] 表示面对 piles[i..j] 这段石子时，当前玩家比对手多得的最大分数差。
转移方程
dp[i][j] = max(
piles[i] - dp[i+1][j], # 取左边
piles[j] - dp[i][j-1] # 取右边
)
直觉理解：如果我取了 piles[i]，对手面对 piles[i+1..j]，对手的最优分差是 dp[i+1][j]。从我的视角看，对手多得的等于我少得的，所以减去它。
完整代码
def stone_game(piles: list[int]) -> bool:
"""石子游戏：区间博弈 DP"""
n = len(piles)
# dp[i][j]: 面对 piles[i..j] 时，当前玩家比对手多得的最大分差
dp = [[0] * n for _ in range(n)]
# 基础情况：只有一堆石子时，当前玩家全取
for i in range(n):
dp[i][i] = piles[i]
# 按区间长度从短到长填表
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = max(
piles[i] - dp[i + 1][j],
piles[j] - dp[i][j - 1]
)
return dp[0][n - 1] > 0
时间复杂度：O(n^2)。空间复杂度：O(n^2)。
LeetCode #877 的数学捷径
实际上，对于 LeetCode #877 的特定条件（偶数堆、总数为奇数），先手永远可以赢。因为先手可以选择"只取奇数位"或"只取偶数位"（按照堆的下标奇偶分组），而这两组的总和一定不相等（总和为奇数），先手选择总和大的那组即可。
但上面的 DP 解法是通用的，适用于任何变体。
29.7 树形 DP 的更多例子
所有可能的满二叉树（LeetCode #894）
满二叉树：每个节点要么是叶子，要么有两个子节点。给定节点数 n，返回所有可能的满二叉树。
这个问题的关键观察：满二叉树的节点数一定是奇数（根 + 左子树 + 右子树，左右子树节点数都是奇数）。如果 n 为偶数，答案为空。
from functools import lru_cache
from typing import Optional, List
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def all_possible_fbt(n: int) -> List[Optional[TreeNode]]:
"""所有可能的满二叉树"""
@lru_cache(maxsize=None)
def build(num_nodes: int) -> List[Optional[TreeNode]]:
if num_nodes == 1:
return [TreeNode(0)]
if num_nodes % 2 == 0:
return []
result = []
# 枚举左子树的节点数（奇数）
for left_count in range(1, num_nodes - 1, 2):
right_count = num_nodes - 1 - left_count
left_trees = build(left_count)
right_trees = build(right_count)
for lt in left_trees:
for rt in right_trees:
root = TreeNode(0)
root.left = lt
root.right = rt
result.append(root)
return result
return build(n)
Level 3 · 规范怎么定义的
29.8 状压 DP 的复杂度分析
为什么是 O(n * 2^n)？
状压 DP 的状态空间由两部分组成：
- 子集枚举：n 个元素的所有子集共 2^n 个
- 每个子集中需要一个额外维度：通常是"当前在哪个元素"，共 n 种选择
因此状态总数为 n * 2^n。转移时，通常枚举从哪个元素转移来，再乘一个 n，得到 O(n^2 * 2^n)。
与全排列的对比
| 方法 | 时间复杂度 | n=15 | n=20 |
|---|---|---|---|
| 暴力全排列 | O(n!) | 1.3 * 10^12 | 2.4 * 10^18 |
| 状压 DP | O(n^2 * 2^n) | 7.4 * 10^6 | 4.2 * 10^8 |
对于 n=20，状压 DP 比暴力快了 10^10 倍！这就是 Held-Karp 算法（1962 年）的威力。
Held-Karp 算法的历史
Michael Held 和 Richard Karp 在 1962 年发表论文 "A Dynamic Programming Approach to Sequencing Problems"（Journal of the Society for Industrial and Applied Mathematics），首次将状态压缩与动态规划结合，把 TSP 的精确求解复杂度从 O(n!) 降到 O(n^2 * 2^n)。虽然仍是指数级，但这是 TSP 精确算法的最优已知复杂度（在合理假设下无法改进）。
枚举子集的子集
有些状压 DP 需要枚举一个集合的所有子集。一种常见模式：
# 枚举 mask 的所有非空子集
sub = mask
while sub > 0:
# 处理子集 sub
sub = (sub - 1) & mask
这段代码的复杂度是多少？ 对于一个固定的 mask（假设有 k 个 1），它枚举 2^k - 1 个非空子集。如果对所有 mask 都执行这个枚举，总复杂度为：
$$\sum_{k=0}^{n} \binom{n}{k} \cdot 2^k = 3^n$$
这来自二项式定理 $(1+2)^n = 3^n$。所以"对所有子集枚举其子集"的总复杂度是 O(3^n)，不是 O(4^n)。
29.9 Sprague-Grundy 定理
博弈论基础
组合博弈论（Combinatorial Game Theory）研究的是两个玩家轮流操作、完全信息、无随机因素的博弈。在这类博弈中，每个局面要么是 N-position（下一个行动的人必胜），要么是 P-position（上一个行动的人必胜，即当前行动者必败）。
Sprague-Grundy 值
每个博弈局面可以赋一个非负整数 g（Grundy 值或 nimber）：
- 终止局面（无法操作）的 Grundy 值为 0
- 其他局面的 Grundy 值等于其所有后继局面的 Grundy 值的 mex（最小排斥值）
$$g(x) = \text{mex}{g(y) : y \text{ 是 } x \text{ 的后继}}$$
其中 mex（minimal excludant）是不在给定集合中的最小非负整数。
Sprague-Grundy 定理的内容
由 Roland Sprague（1935 年）和 Patrick Grundy（1939 年）独立发现：
定理：一个组合博弈等价于一个 Nim 堆，其大小等于该博弈的 Grundy 值。多个独立博弈的组合，其 Grundy 值等于各子博弈 Grundy 值的 XOR（异或）。
为什么重要？ 这个定理把任何有限无循环的公平博弈（impartial game）归约为 Nim 游戏。只要能算出每个子博弈的 Grundy 值，整个组合博弈的胜负就能通过异或运算判断。
经典 Nim 游戏的 SG 分析
多堆石子的 Nim 游戏：有 k 堆石子，数量分别为 n_1, n_2, ..., n_k，两人轮流从任意一堆中取任意数量。
每堆石子是一个独立的子博弈，大小为 n_i 的 Nim 堆的 Grundy 值就是 n_i 本身。
整个博弈的 Grundy 值 = n_1 XOR n_2 XOR ... XOR n_k。
- 如果异或结果 != 0，先手必胜（N-position）
- 如果异或结果 == 0，后手必胜（P-position）
代码验证
def compute_grundy(n: int, max_take: int) -> int:
"""
计算取石子博弈的 Grundy 值
一堆 n 个石子，每次最多取 max_take 个
"""
grundy = [0] * (n + 1)
for i in range(1, n + 1):
reachable = set()
for take in range(1, min(i, max_take) + 1):
reachable.add(grundy[i - take])
# mex: 最小的不在 reachable 中的非负整数
mex = 0
while mex in reachable:
mex += 1
grundy[i] = mex
return grundy[n]
# 验证：每次最多取 3 个时，Grundy 值 = n % 4
for n in range(20):
assert compute_grundy(n, 3) == n % 4
SG 定理在面试中的应用
面试中遇到博弈题，解题思路：
- 先找小情况的规律（列表找 P/N position）
- 如果是多个独立子博弈的组合，算各子博弈 Grundy 值然后异或
- 很多题目实际上不需要完整 SG 分析，直接找规律或用数学结论即可
29.10 数位 DP 的理论基础
数位 DP 的正确性证明
数位 DP 的核心是把"统计 [0, n] 内满足条件的数"转化为"逐位决策"。其正确性基于以下观察：
对于一个 d 位数 n = a_{d-1} a_{d-2} ... a_1 a_0，[0, n] 内的任何数 x 可以唯一分解为：
- 存在某一位 k，使得 x 的前 d-1-k 位等于 n 的前 d-1-k 位，而第 k 位严格小于 n 的第 k 位
这正是 tight 标记的含义：tight = True 表示"前面所有位都贴着上界"，一旦某位选了比上界小的数字，tight 变为 False，之后的位完全自由。
记忆化的有效性
数位 DP 使用记忆化搜索时，状态 (pos, count, tight, started) 中：
pos有 d 种取值count取决于具体问题（对"1的个数"问题，最大为 d）tight只有 True/Falsestarted只有 True/False
总状态数 = O(d^2 * 4) = O(d^2)，这是极小的——数位 DP 的效率非常高。
Level 4 · 边界与陷阱
29.11 面试题详解：打家劫舍 III（#337）
面试中的陷阱
-
递归爆栈：如果树极度不平衡（退化为链表），递归深度可能达到 O(n)。Python 默认递归深度 1000，需要
sys.setrecursionlimit。 -
返回值设计：很多人初次尝试会写
dfs(node, robbed)表示"当前节点是否被偷"，这会导致状态爆炸。正确做法是每个节点返回元组(rob, not_rob)。 -
面试官追问：如果不是二叉树呢？ 同样的思路，但
not_rob的计算变为所有子节点的max(rob_child, not_rob_child)之和：
def rob_general_tree(root):
"""通用树（多叉树）的打家劫舍"""
def dfs(node):
if not node:
return (0, 0)
rob_sum = node.val
not_rob_sum = 0
for child in node.children:
child_rob, child_not = dfs(child)
rob_sum += child_not
not_rob_sum += max(child_rob, child_not)
return (rob_sum, not_rob_sum)
r, nr = dfs(root)
return max(r, nr)
29.12 面试题详解：最短超级串（#943）
问题描述
给定一个字符串数组 words，找到包含每个字符串作为子串的最短字符串。
分析
这本质上是 TSP 的变体！把每个字符串看作一个"城市"，从字符串 A 到字符串 B 的"距离"定义为把 B 接在 A 后面时需要新增的字符数（即 B 去掉与 A 后缀重叠的部分后剩余的长度）。
步骤：
- 预处理：计算任意两个字符串之间的重叠长度
- 状压 DP：类似 TSP，找到最优的字符串排列顺序
- 路径重建：根据 DP 结果构造最终字符串
完整代码
def shortest_superstring(words: list[str]) -> str:
"""最短超级串：状压 DP"""
n = len(words)
# 预处理：overlap[i][j] = words[i] 的后缀与 words[j] 的前缀的最大重叠长度
overlap = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
if i == j:
continue
# 找 words[i] 的后缀与 words[j] 的前缀的最大重叠
max_k = min(len(words[i]), len(words[j]))
for k in range(max_k, 0, -1):
if words[i].endswith(words[j][:k]):
overlap[i][j] = k
break
# 状压 DP
# dp[mask][i] = 已选 mask 中的字符串，最后一个是 words[i] 时的最大总重叠
dp = [[0] * n for _ in range(1 << n)]
parent = [[-1] * n for _ in range(1 << n)] # 路径追踪
for mask in range(1, 1 << n):
for i in range(n):
if not (mask >> i & 1):
continue
prev_mask = mask ^ (1 << i)
if prev_mask == 0:
continue # i 是第一个选的
for j in range(n):
if not (prev_mask >> j & 1):
continue
val = dp[prev_mask][j] + overlap[j][i]
if val > dp[mask][i]:
dp[mask][i] = val
parent[mask][i] = j
# 找最优终点
full_mask = (1 << n) - 1
last = max(range(n), key=lambda i: dp[full_mask][i])
# 路径重建
path = []
mask = full_mask
cur = last
while cur != -1:
path.append(cur)
prev = parent[mask][cur]
mask ^= (1 << cur)
cur = prev
path.reverse()
# 构造结果字符串
result = words[path[0]]
for k in range(1, len(path)):
i, j = path[k - 1], path[k]
result += words[j][overlap[i][j]:]
return result
复杂度：O(n^2 * 2^n)，n <= 12 时可行。
29.13 面试题详解：所有可能的满二叉树（#894）
面试要点
-
递归 + 记忆化：关键观察是 n 为偶数时无解，n=1 时只有一个节点。对于 n>=3，枚举左子树大小 1, 3, 5, ..., n-2。
-
面试官常见追问：
- "时间复杂度是多少？"——这是 Catalan 数的一个变体，满二叉树的数量是 Catalan(n/2)，约为 4^(n/2) / (n/2)^(3/2)
- "能否迭代实现？"——可以用自底向上的方式，从 n=1 开始逐步构建
-
注意引用共享：在记忆化版本中，返回的子树可能被多个父节点引用。如果题目要求返回所有不同的树（而非修改树），这没问题。但如果后续要修改返回的树，需要深拷贝。
# 迭代版本
def all_possible_fbt_iterative(n: int) -> list:
"""自底向上构建所有满二叉树"""
if n % 2 == 0:
return []
# dp[i] = 所有有 i 个节点的满二叉树
dp = [[] for _ in range(n + 1)]
dp[1] = [TreeNode(0)]
for total in range(3, n + 1, 2):
for left in range(1, total - 1, 2):
right = total - 1 - left
for lt in dp[left]:
for rt in dp[right]:
root = TreeNode(0, lt, rt)
dp[total].append(root)
return dp[n]
29.14 状压 DP 的工程实践建议
Python 中的状压 DP 优化
-
位运算替代集合操作：Python 的 set 虽然方便，但在状压 DP 中用整数位运算更快一个数量级。
-
预计算 popcount：
popcount = [bin(i).count('1') for i in range(1 << n)]
-
降维优化：如果 dp[mask] 只依赖 popcount(mask) 较小的状态，可以按 popcount 分层处理。
-
注意整数溢出：Python 的整数无上限，但在其他语言中 n > 30 时 2^n 会溢出 32 位整数。面试中要说明这点。
面试中的典型陷阱
| 陷阱 | 说明 | 解决方法 |
|---|---|---|
| mask 枚举顺序 | 从小到大枚举 mask 即可保证依赖关系 | 确保 dp[mask] 计算时其子集已就绪 |
| 起始状态遗漏 | TSP 中忘记设 dp[1][0]=0 | 仔细定义"初始只包含起点"的状态 |
| 回到起点 | TSP 最后要加回起点的距离 | 别忘了 + dist[last][0] |
| 对称性 | 有些问题中(A,B)和(B,A)等价 | 可以固定起点节省一半时间 |
29.15 综合对比：何时用哪种 DP
| 问题特征 | DP 类型 | 典型题目 |
|---|---|---|
| 树结构上的最优化 | 树形 DP | 打家劫舍III、树的最长路径 |
| 集合选取顺序相关 | 状压 DP | TSP、最短超级串 |
| 统计数值范围内的计数 | 数位 DP | 数字1的个数、不含连续1的非负整数 |
| 两人轮流博弈 | 博弈 DP | 石子游戏、Nim |
| 两个序列的关系 | 序列 DP | LCS、编辑距离 |
| 区间合并/分割 | 区间 DP | 矩阵链乘法、戳气球 |
面试中遇到 DP 题，先判断属于哪一类，再套用对应的状态定义模板——这比从零开始设计状态要快得多。
本章小结
-
树形 DP 的核心是后序遍历：先算子树，再合并到父节点。状态通常需要拆分（如"选/不选当前节点"）。
-
状压 DP 用位掩码编码集合状态，把 O(n!) 问题降到 O(n^2 * 2^n)。适用于 n <= 20 的全排列/全选择问题。
-
数位 DP 逐位决策，用 tight 约束保证不超上界。适用于统计区间内满足特定条件的数。
-
博弈 DP 中，Sprague-Grundy 定理把任意公平博弈归约为 Nim 游戏，多个独立子博弈取异或。
-
面试策略：先分类（看问题特征），再套模板（状态定义 + 转移方程），最后验证（小例子手算）。