动态规划专题
概述
本章介绍超越基础动态规划的进阶技巧，包括树形DP、状态压缩DP、数位DP、概率/期望DP、博弈DP以及DP优化方法。每个主题配有经典问题和解题思路。
1. 树形DP
1.1 基本思想
在有根树上进行DP，状态定义在子树上，自底向上合并子节点信息。
1.2 经典问题：树的最大独立集
给定 \(n\) 个节点的树，选择尽可能多的节点，使任意两个被选节点不相邻。
状态定义：
- \(dp[v][0]\)：不选节点 \(v\) 时，以 \(v\) 为根的子树的最大独立集大小
- \(dp[v][1]\)：选节点 \(v\) 时，以 \(v\) 为根的子树的最大独立集大小
转移方程：
def tree_max_independent_set(adj, root=0):
"""树的最大独立集"""
n = len(adj)
dp = [[0, 0] for _ in range(n)]
visited = [False] * n
# 后序遍历（DFS）
stack = [(root, False)]
parent = [-1] * n
order = []
visited[root] = True
while stack:
v, processed = stack.pop()
if processed:
order.append(v)
continue
stack.append((v, True))
for u in adj[v]:
if not visited[u]:
visited[u] = True
parent[u] = v
stack.append((u, False))
for v in order:
dp[v][1] = 1
for u in adj[v]:
if u != parent[v]:
dp[v][0] += max(dp[u][0], dp[u][1])
dp[v][1] += dp[u][0]
return max(dp[root][0], dp[root][1])
1.3 树的直径
两次BFS法：从任意点BFS找最远点 \(u\)，再从 \(u\) BFS找最远点 \(v\)，\(d(u,v)\) 即为直径。
树形DP法：
def tree_diameter(adj, root=0):
"""树形DP求直径"""
n = len(adj)
depth1 = [0] * n # 最长链
depth2 = [0] * n # 次长链
diameter = 0
# 后序遍历
# ...（类似上面的DFS）
for v in order:
for u in adj[v]:
if u != parent[v]:
d = depth1[u] + 1
if d > depth1[v]:
depth2[v] = depth1[v]
depth1[v] = d
elif d > depth2[v]:
depth2[v] = d
diameter = max(diameter, depth1[v] + depth2[v])
return diameter
1.4 换根DP（rerooting）
有时需要求"以每个节点为根时"的答案。
技巧：先以某个节点为根做一次DP，再通过父子关系转移（换根），\(O(n)\) 得到所有根的答案。
2. 状态压缩DP（状压DP）
2.1 基本思想
当问题涉及集合的状态时，用二进制位表示集合中元素的选择状态。
状态空间：\(2^n\)（\(n\) 为集合大小，通常 \(n \leq 20\)）。
2.2 经典问题：旅行商问题（TSP）
给定 \(n\) 个城市和距离矩阵，求经过所有城市恰好一次并返回起点的最短回路。
状态定义：
- \(dp[S][i]\)：已访问城市集合为 \(S\)，当前在城市 \(i\) 的最短路径长度
转移方程：
初始条件：\(dp[\{0\}][0] = 0\)
答案：\(\min_{i} \left\{ dp[\text{ALL}][i] + d(i, 0) \right\}\)
def tsp_bitmask(dist):
"""状压DP解TSP"""
n = len(dist)
INF = float('inf')
ALL = (1 << n) - 1
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0 # 从城市0出发
for S in range(1, 1 << n):
for i in range(n):
if dp[S][i] == INF:
continue
if not (S >> i & 1):
continue
for j in range(n):
if S >> j & 1: # j已在S中
continue
new_S = S | (1 << j)
dp[new_S][j] = min(dp[new_S][j], dp[S][i] + dist[i][j])
return min(dp[ALL][i] + dist[i][0] for i in range(n))
时间复杂度：\(O(2^n \cdot n^2)\)
空间复杂度：\(O(2^n \cdot n)\)
2.3 经典问题：子集枚举
枚举集合 \(S\) 的所有子集：
# 枚举S的所有非空子集
sub = S
while sub > 0:
# 处理子集 sub
process(sub)
sub = (sub - 1) & S
总枚举量：\(\sum_{k=0}^{n} \binom{n}{k} 2^k = 3^n\)
2.4 经典问题：分配问题
\(n\) 个人分配 \(n\) 项任务，每人恰好一项，最小化总代价。
其中 \(|S|\) 表示已分配的人数。
3. 数位DP
3.1 基本思想
数位DP用于计算满足特定数字性质的整数个数（在 \([0, N]\) 或 \([L, R]\) 范围内）。
核心要素：
- 逐位确定数字
- 维护
tight标志（是否受上界约束） - 可能需要
leading_zero标志
3.2 通用框架
from functools import lru_cache
def count(N):
"""计算[0, N]中满足条件的整数个数"""
digits = list(map(int, str(N)))
n = len(digits)
@lru_cache(maxsize=None)
def dp(pos, tight, state):
"""
pos: 当前处理第几位
tight: 是否受上界约束
state: 问题特定的状态
"""
if pos == n:
return 1 if is_valid(state) else 0
limit = digits[pos] if tight else 9
result = 0
for d in range(0, limit + 1):
new_tight = tight and (d == limit)
new_state = update_state(state, d)
result += dp(pos + 1, new_tight, new_state)
return result
return dp(0, True, initial_state)
3.3 经典问题：统计 \([1, N]\) 中数字1出现的次数
状态：\((pos, tight, count\_of\_1)\)
3.4 经典问题：\([L, R]\) 中不含相邻相同数字的整数个数
状态：\((pos, tight, last\_digit, leading\_zero)\)
def count_no_adjacent(N):
digits = list(map(int, str(N)))
n = len(digits)
@lru_cache(maxsize=None)
def dp(pos, tight, last, leading_zero):
if pos == n:
return 1
limit = digits[pos] if tight else 9
result = 0
for d in range(0, limit + 1):
if not leading_zero and d == last:
continue # 跳过相邻相同
new_lz = leading_zero and (d == 0)
new_last = -1 if new_lz else d
result += dp(pos + 1, tight and (d == limit), new_last, new_lz)
return result
return dp(0, True, -1, True)
4. 概率/期望DP
4.1 基本思想
状态表示概率或期望值，转移方程中包含概率权重。
期望DP的常见模式：
4.2 经典问题：收集优惠券问题
\(n\) 种优惠券，每次等概率获得一种，期望多少次能收集齐所有种类？
状态：\(dp[i]\) = 已有 \(i\) 种时，收集到 \(i+1\) 种的期望次数。
总期望：
4.3 经典问题：随机游走
在图上从起点到终点的期望步数。
状态：\(E[v]\) = 从 \(v\) 出发到达终点的期望步数。
转移：
对终点 \(t\)：\(E[t] = 0\)。
这是一个线性方程组，可用高斯消元求解。
4.4 经典问题：概率DP
在DAG上，从 \(s\) 到 \(t\) 的路径中，边权和大于 \(W\) 的概率。
状态：\(p[v][w]\) = 从 \(v\) 出发，剩余预算为 \(w\) 时到达 \(t\) 的概率。
5. 博弈DP
5.1 Sprague-Grundy定理
核心思想：任何无偏二人有限博弈（Impartial Game）都等价于一个Nim游戏。
Grundy值（SG值）：
其中 \(\text{mex}(S)\) 是最小不属于 \(S\) 的非负整数。
- \(\text{SG}(v) = 0\)：必败态（后手胜）
- \(\text{SG}(v) > 0\)：必胜态（先手胜）
5.2 Nim游戏
\(n\) 堆石子，数量分别为 \(a_1, a_2, \ldots, a_n\)，两人轮流从某堆取若干石子，取完最后一颗的人获胜。
Bouton定理：先手必胜当且仅当：
其中 \(\oplus\) 是异或运算。
def nim_winner(piles):
"""Nim游戏：返回先手是否必胜"""
xor_sum = 0
for p in piles:
xor_sum ^= p
return xor_sum != 0
5.3 SG定理的应用
多个独立子游戏的组合：
例：多堆取石子游戏，每堆最多取 \(k\) 个：
5.4 经典博弈DP问题
硬币博弈：\(n\) 个硬币排成一行，值为 \(v_1, \ldots, v_n\)，两人轮流从两端取一个，最大化自己的总值。
状态：\(dp[i][j]\) = 剩余硬币为 \(v_i, \ldots, v_j\) 时，先手能获得的最大值。
或者更简洁地：
其中 \(\text{sum}(i,j) = v_i + \cdots + v_j\)。
6. DP优化
6.1 凸包技巧（Convex Hull Trick）
适用于转移方程形如：
其中 \(b[j]\) 单调，\(a[i]\) 单调。
思想：将每个 \(j\) 看作直线 \(y = b[j] \cdot x + dp[j]\)，维护下凸包，在 \(x = a[i]\) 处查询最小值。
class ConvexHullTrick:
"""凸包技巧（斜率单调递减，查询点单调递增）"""
def __init__(self):
self.lines = [] # [(slope, intercept)]
self.ptr = 0
def bad(self, l1, l2, l3):
"""l2是否被l1和l3淘汰"""
return (l3[1] - l1[1]) * (l1[0] - l2[0]) <= (l2[1] - l1[1]) * (l1[0] - l3[0])
def add_line(self, slope, intercept):
line = (slope, intercept)
while len(self.lines) >= 2 and self.bad(self.lines[-2], self.lines[-1], line):
self.lines.pop()
self.lines.append(line)
def query(self, x):
"""查询x处的最小值（x单调递增时使用指针）"""
while self.ptr < len(self.lines) - 1:
if self.lines[self.ptr][0] * x + self.lines[self.ptr][1] > \
self.lines[self.ptr + 1][0] * x + self.lines[self.ptr + 1][1]:
self.ptr += 1
else:
break
return self.lines[self.ptr][0] * x + self.lines[self.ptr][1]
时间复杂度：均摊 \(O(n)\)（单调情况），\(O(n \log n)\)（非单调需二分）。
6.2 分治优化
适用于转移方程：
其中决策点 \(opt[i][j]\) 满足单调性：\(opt[i][j] \leq opt[i][j+1]\)。
条件：代价函数 \(C\) 满足四边形不等式：
分治实现：
def solve(dp_prev, dp_curr, lo, hi, opt_lo, opt_hi, cost):
"""分治DP优化"""
if lo > hi:
return
mid = (lo + hi) // 2
best_k = opt_lo
best_val = float('inf')
for k in range(opt_lo, min(mid, opt_hi) + 1):
val = dp_prev[k - 1] + cost(k, mid) if k > 0 else cost(0, mid)
if val < best_val:
best_val = val
best_k = k
dp_curr[mid] = best_val
solve(dp_prev, dp_curr, lo, mid - 1, opt_lo, best_k, cost)
solve(dp_prev, dp_curr, mid + 1, hi, best_k, opt_hi, cost)
时间复杂度：\(O(kn \log n)\)（\(k\) 层，\(n\) 个状态）。
6.3 斜率优化
本质上是凸包技巧的推广。将转移方程改写为：
转化为：点 \((x_i, y_i)\) 和查询斜率 \(k_j\) 的几何问题。
6.4 Knuth优化
适用于最优二叉搜索树类问题：
Knuth定理：若 \(w\) 满足四边形不等式，则 \(opt[i][j-1] \leq opt[i][j] \leq opt[i+1][j]\)。
利用决策点单调性，可将 \(O(n^3)\) 优化到 \(O(n^2)\)。
7. DP优化总结
| 优化方法 | 适用条件 | 复杂度提升 |
|---|---|---|
| 凸包技巧 | 线性转移、斜率/查询单调 | \(O(n^2) \to O(n)\) |
| 分治优化 | 决策点单调 | \(O(kn^2) \to O(kn\log n)\) |
| Knuth优化 | 区间DP + 四边形不等式 | \(O(n^3) \to O(n^2)\) |
| 斜率优化 | 转移可线性化 | \(O(n^2) \to O(n)\) 或 \(O(n\log n)\) |
| 数据结构优化 | 区间查询/更新 | 视具体结构而定 |
graph TD
DP[动态规划优化] --> CHT[凸包技巧]
DP --> DC[分治优化]
DP --> KNUTH[Knuth优化]
DP --> DS[数据结构优化]
CHT --> CHT1[斜率单调: O-n]
CHT --> CHT2[斜率非单调: O-n-log-n]
DC --> DC1[决策点单调]
DC --> DC2[四边形不等式]
KNUTH --> KNUTH1[区间DP]
DS --> SEG[线段树]
DS --> BIT[树状数组]
DS --> DEQUE[单调队列/栈]
8. 练习题推荐
| 类型 | 题目 | 核心技巧 |
|---|---|---|
| 树形DP | 树的最大独立集 | 选/不选两种状态 |
| 树形DP | 树的中心 | 换根DP |
| 状压DP | TSP | \(dp[S][i]\)，\(O(2^n n^2)\) |
| 状压DP | 棋盘覆盖 | 行状态压缩 |
| 数位DP | 数字计数 | \([L,R]\) 分解 |
| 期望DP | 收集优惠券 | 调和级数 |
| 博弈DP | Nim游戏 | SG定理 |
| 凸包技巧 | 分段线性代价 | 维护凸包 |
| 分治优化 | \(k\)段最小代价 | 决策点单调 |
参考资料
- Cormen et al., Introduction to Algorithms (CLRS), Chapters 15-16
- Competitive Programming 3 (CP3), Chapter 3 & 8
- Halim & Halim, Competitive Programming
- OI Wiki (oi-wiki.org)
相关章节：