本讲定位：前五讲的状态都能用”几个数”描述——下标、容量、区间端点、子树根。本讲面对一类新问题：必须记住”选了哪些”，而这份名单没法压缩成几个数。解决办法是把整个集合塞进一个二进制整数，让”集合”也能当数组下标——这就是状态压缩（状压）DP。学完本讲，旅行商类、棋盘放置类问题都有了统一框架。
前置知识：专题一（记忆化→递推、依赖决定顺序）、专题五（“缺信息就加维”，第 5 节呼应）；位运算基础（本讲第 2 节会集中复习）。
标注 ⭐ 的小节为进阶内容，第一遍学可以跳过。
看这道题（洛谷 P1433 吃奶酪）：平面上有 $n \le 15$ 块奶酪，从原点 $(0,0)$ 出发把它们全部吃完，问走过的路程最短是多少。
按 DP 的老套路想：走到中途，未来的决策取决于什么？
第一条好办，一个编号就行。第二条麻烦了——试着压缩它：只记”还剩几块没吃”行不行？不行。同样是”剩 3 块”，剩的是家门口的 3 块还是天边的 3 块，后面要走的路完全不同。未来真的依赖”具体是哪些”，这个信息一位都省不掉。
那就别省了，直接把集合存进状态。关键观察：
一个 $n$ 元集合的子集，恰好对应一个 $n$ 位二进制数：第 $i$ 位是 $1$ 表示元素 $i$ 在集合里。集合就是一个 $[0, 2^n)$ 的整数，当然能当数组下标。
代价是状态数 $2^n$——所以状压题的 $n$ 都很小。看到 $n \le 15 \sim 20$（或棋盘一边 $\le 10$ 出头），就要条件反射地想到状压。 这是数据范围反推算法的典型案例：$2^{15} = 32768$，乘上一两个 $n$ 的系数正好卡在 $10^7 \sim 10^8$ 量级。
状压 DP 的全部”集合语言”就这几句，务必烂熟：
| 集合含义 | 位运算写法 |
|---|---|
| 全集 $\{0,1,\ldots,n-1\}$ | (1 << n) - 1 |
| 判断 $i$ 是否在 $S$ 中 | S >> i & 1 |
| 把 $i$ 加入 $S$ | S | (1 << i) |
| 把 $i$ 移出 $S$ | S & ~(1 << i) |
| 集合大小（1 的个数） | __builtin_popcount(S) |
| 取最低位的 1（lowbit） | S & -S |
| 判断 $S$ 中有无相邻元素 | S & (S << 1)（非零即有） |
| 两集合是否相交 | S & T（非零即相交） |
| $S$ 是否是 $T$ 的子集 | (S & T) == S |
两个高频坑，先打预防针：
== 比 & 优先级高，S & 1 == 0 实际是 S & (1 == 0)，恒为 0。位运算表达式一律多加括号。1 << i 是 int，$i \ge 31$ 就溢出了，要写 1LL << i。本讲 $n \le 20$ 没事，但省选题里集合配合 long long 计数时常踩这个坑。