子集动态规划

状态空间 ​

动态规划公理库动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。以 (S\subseteq U) 为状态，必要时再加终点、容量或边界摘要。它适合子问题只依赖更小子集、而不同排列能汇入同一摘要的精确指数算法。

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

Hamilton 路状态与证明 ​

令 (dp[S,v]) 表示存在一条恰好访问 (S)、终点为 (v) 的简单路径。基例为 (dp[{v},v]=\mathrm{true})。当 (|S|>1) 时， [ dp[S,v] =\bigvee_{\substack{u\in S\setminus{v}\uv\in E}} dp[S\setminus{v},u]. ]

必要性来自删除目标路径的最后一条边：前驱必为某个相邻 (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)) 状态共有 (n2^{n-1}) 个，每个最多枚举 (n) 个前驱，所以直接时间为 (O(n^22^n))，空间为 (O(n2^n))。按邻接 bitset 过滤前驱能改善常数或字操作数，却不改变这一指数状态规模。

枚举量推导 ​

子掩码循环 [ T=S,\qquad T=(T-1)\mathbin{&}S ] 会枚举全部 (T\subseteq S)。对一对 ((T,S))，每个元素恰有“不属于 (S)”“属于 (S\setminus T)”“属于 (T)”三种状态，因此 [ \sum_{S\subseteq U}2^{|S|}=3^n. ] 位技巧让一次得到下个子掩码很便宜，却不能把总转移数写成 (O(n2^n))。

表示与恢复 ​

当 (n\le w) 时，bitmask 可放入一个机器字；更大的宇宙需要多字位集，集合差、成员测试和哈希都要计入字操作成本。按 (|S|) 分层可为只依赖上一层的 DP 滚动空间，但 Hamilton 路重构仍需父信息或第二次计算。

(n=50) 时 (2^n) 已远超常规内存，位运算常数不会改变可行性。Meet-in-the-middle 依赖两半之间可组合的摘要，subset DP 依赖重叠子集状态；Held–Karp TSP 则把布尔可达改为以终点为索引的最小费用。它们都是精确指数算法，不能因使用 bitmask 就称为伪多项式或固定参数可解。

参考资料

• Held, Karp, “A Dynamic Programming Approach to Sequencing Problems,” 1962.
• Björklund et al., “Fourier Meets Möbius,” STOC 2007.
• Cygan et al., Parameterized Algorithms, 2015.