跳到主要内容

状态压缩动态规划

本节目标

用二进制位表示有限集合的选择和轮廓。

识别信号​

对象数量较小，关键历史可以写成集合或一列轮廓；位的含义和基本操作可回顾位运算基础。

状态定义与转移推导​

mask 记录已访问点或未完成轮廓，状态中的第二维记录最后位置或下一列占用。转移只改变一位或生成合法下一轮廓。

初始化与遍历顺序​

Hamilton 从仅含起点的集合开始；轮廓 DP 从空轮廓开始，逐列把所有合法下一状态累加。

通用模板​

dp[startMask][start] = 0
for mask:
  for last in mask:
    extend to every unselected next

空间优化与复杂度​

集合 DP 常为 O(2^n n) 空间和 O(2^n n²) 时间，必须用 int 控制 Hamilton 的内存边界；轮廓宽度应取较短边。

母题序列​

  1. 最短 Hamilton 路径（拓展）：集合加终点状态。
  2. 蒙德里安的梦想（拓展）：列轮廓转移与 64 位计数。

常见误区​

把起点或终点当作可任意选择、使用过小无穷大，或把更长边作为轮廓宽度。

迁移方向​

当状态来自数位前缀而非集合时转向数位 DP；本章不引入插头 DP。