子集动态规划

形式陈述 ​

状态空间 ​

给定含 $n$ 个元素的有限全集理路有限集Finite set与某个自然数初始段等势、因而能够在有限步内无遗漏编号的集合。 $U$，子集动态规划以子集理路子集Subset · Set inclusionA 的每个元素都属于 B 时成立的包含关系；它在集合之间形成偏序。 $S\subseteq U$ 为状态，必要时再加终点、容量或边界摘要。它沿用动态规划理路动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。的重叠子问题原则，适合子问题只依赖更小子集、而不同排列能汇入同一摘要的精确指数算法。

状态数 $2^n$ 不等于运行时间。若每个 $S$ 只枚举其中的元素，总量为 $O(n{2}^n)$；若每个 $S$ 枚举全部 $T\subseteq S$，转移数会增长到 $3^n$。

Hamilton 路状态与证明 ​

给定顶点集为 $U$、$n\ge 1$ 的有限简单无向图 $G=(U,E)$。令 $dp[S,v]$（$v\in S$）表示存在一条恰好访问 $S$、终点为 $v$ 的简单路径。基例为 $dp[\{v\},v]=\mathrm{true}$。当 $|S|>1$ 时，

必要性来自删除目标路径的最后一条边：前驱必为某个相邻 $u$，余下路径恰访问 $S\setminus \{v\}$。充分性则把 $v$ 接到已有路径末端；由于 $v\notin S\setminus \{v\}$，不会重复顶点。按 $|S|$ 归纳便得到“当且仅当”不变量。

三点路径 $1-2-3$ 中，单点状态为真；$dp[\{1,2\},2]$ 由 1 转移，$dp[\{1,2,3\},3]$ 再由 2 转移。$dp[\{1,3\},3]$ 为假，因为缺少边 13。若要输出路径，父指针还需记录让状态成立的 $u$。

有效 $(S,v)$ 状态共有 $n{2}^{n-1}$ 个，每个最多枚举 $n$ 个前驱，在状态和邻接查询为常数成本时，直接时间为 $O(n^2{2}^n)$，空间为 $O(n{2}^n)$。按邻接 bitset 过滤前驱能改善常数或字操作数，却不改变这一指数状态规模。