02.7.2.3 状态压缩 DP
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.7 动态规划 / 02.7.2 区间树形与状态压缩 DP
02.7.2.3-001 状态压缩的思想是什么?
一句话结论
当状态是一组元素的选取/占用集合时,用整数二进制位掩码表示集合:位 1 表示选中;把集合维度压缩成一个整数下标,存入 DP 表;适合 n 较小(通常 ≤20)的集合类问题。
概念解释
- 掩码:位集合。
- 压缩:集合 → 整数。
原理流程
- 把每个元素对应一位。
- 位运算表达集合操作。
- 掩码作 DP 状态下标。
代码 / 示例
mask = 0b101 表示选了第 0、2 个元素
常见误区
- 误区:n 很大还用掩码;正解:2ⁿ 状态爆炸,受限规模使用。
- 误区:位与元素下标对应混乱;正解:统一 bit i 对应元素 i。
追问
- Q:掩码适用规模? A:n ≤ 20 左右,2ⁿ 可接受。
- Q:不能用整数怎么办? A:位数大用大数或换题型。
02.7.2.3-002 掩码怎么表示集合?
一句话结论
第 i 位为 1 表示元素 i 在集合中;加入元素 mask | (1<<i),移除 mask & ~(1<<i),判断包含 (mask>>i)&1;全集 (1<<n)-1。
概念解释
- 位映射:元素 ↔ bit。
- 集合运算:位运算。
原理流程
- 置位/清位/判位。
- 集合交并差用位与或非。
- 空集为 0。
代码 / 示例
int add = mask | (1 << i);
boolean has = ((mask >> i) & 1) == 1;
int full = (1 << n) - 1;
常见误区
- 误区:移除用异或;正解:与非更稳,避免重复翻转。
- 误区:位移位数超整数宽度;正解:n 控制在整数位内。
追问
- Q:两集合交集? A:
maskA & maskB。 - Q:子集判断? A:
(maskA & maskB) == maskA。
02.7.2.3-003 状态转移怎么枚举子集与未选元素?
一句话结论
从当前掩码出发,枚举未选位加入得到新掩码;或枚举当前掩码子集做转移;常用低位提取 lowbit 遍历元素;转移保证每步加入一个元素,状态无环。
概念解释
- 未选位:掩码 0 的位置。
- 子集枚举:位运算遍历。
原理流程
- 找未选元素 i。
- 新掩码
mask | (1<<i)。 - 更新目标状态。
代码 / 示例
for (int i = 0; i < n; i++)
if (((mask >> i) & 1) == 0)
dp[mask | (1 << i)] = min(...);
常见误区
- 误区:重复加入已选位;正解:先判未选。
- 误区:转移出现环;正解:掩码位只增不减。
追问
- Q:怎么快速枚举子集? A:
sub = (sub-1)&mask递减遍历。 - Q:状态数多少? A:2ⁿ。
02.7.2.3-004 常用位运算技巧有哪些?
一句话结论
低位 lowbit = mask & -mask;位编号 Integer.bitCount;判断全选 mask==full;翻转某位 mask ^ (1<<i);判相邻位 (mask & (mask<<1))==0;这些是状压 DP 的基础操作。
概念解释
- 计数/低位/相邻判断。
- 位运算 O(1)。
原理流程
- 按需求选位运算。
- 避免循环判位。
- 掩码合法性预处理。
代码 / 示例
int cnt = Integer.bitCount(mask);
boolean noAdj = (mask & (mask << 1)) == 0;
常见误区
- 误区:移位方向搞反;正解:左移位编号增大。
- 误区:bitCount 当权重求和;正解:只计选了几个。
追问
- Q:lowbit 对应哪个元素? A:最低位 1 的位置。
- Q:相邻不冲突怎么判? A:mask 与左移一位无交集。
02.7.2.3-005 TSP 旅行商状态怎么设计?
一句话结论
dp[mask][i] 已访问集合 mask、当前在城市 i 的最短路径;枚举未访问城市 j 转移 dp[mask|(1<<j)][j]=min(..., dp[mask][i]+dist[i][j]);起点固定,终态全选后回起点;时间 O(2ⁿ·n²)。
概念解释
- 状态:已访问集合 + 当前位置。
- 末步:下一城市。
原理流程
- 初始化起点状态。
- 枚举掩码与当前城市。
- 扩展未访问城市。
代码 / 示例
for (int mask = 0; mask < (1<<n); mask++)
for (int i = 0; i < n; i++)
if (has(mask,i))
for (int j = 0; j < n; j++)
if (!has(mask,j))
dp[mask|(1<<j)][j] = Math.min(dp[...], dp[mask][i]+dist[i][j]);
常见误区
- 误区:状态只记当前城市;正解:需记录已访问集合避免重复。
- 误区:忘记回起点成本;正解:TSP 终点需回到起点。
追问
- Q:复杂度? A:O(2ⁿ·n²),空间 O(2ⁿ·n)。
- Q:n 上限? A:约 12~15 常规可跑。
02.7.2.3-006 最短 Hamilton 路径与 TSP 区别?
一句话结论
Hamilton 路径不要求回到起点,终态全选任一城市即可取最小;TSP 是回路,终态还要加回起点距离;状态转移框架相同,仅终点口径不同。
概念解释
- 路径:终点不回起点。
- 回路:终点回起点。
原理流程
- 同 TSP 填表。
- 路径取全选各城市最小。
- 回路加返程距离。
代码 / 示例
路径:min_i dp[full][i]
回路:min_i dp[full][i] + dist[i][start]
常见误区
- 误区:路径也加返程;正解:路径不回起点。
- 误区:起点不固定无法处理? A:可枚举起点或状态含起点。
追问
- Q:复杂度? A:同 TSP O(2ⁿ·n²)。
- Q:Hamilton 回路存在性? A:布尔 DP 判断可达。
02.7.2.3-007 相邻不冲突的放置问题怎么状压?
一句话结论
每行放置方案用掩码表示,行内相邻不冲突(mask & mask<<1 == 0);相邻行掩码无同列冲突(a & b == 0);dp[row][mask] 前 row 行该放置方案的最优/计数;逐行转移。
概念解释
- 行掩码:本行占用列。
- 行间约束:列不重叠。
原理流程
- 预处理合法行掩码。
- 逐行枚举上一行兼容掩码。
- 转移累加/取优。
代码 / 示例
if ((prev & cur) == 0 && noAdj(cur)) dp[r][cur] += dp[r-1][prev];
常见误区
- 误区:只判行内相邻;正解:行间同列也要判。
- 误区:未预处理非法行;正解:先筛合法掩码减少转移。
追问
- Q:放国王类还有对角约束;正解:再判
cur & (prev<<1)、cur & (prev>>1)。 - Q:复杂度? A:O(rows·2ⁿ·2ⁿ),合法掩码优化后下降。
02.7.2.3-008 棋盘铺地砖/放国王怎么状压?
一句话结论
铺砖按行轮廓掩码记录已被上一行砖占用的格子;放国王记录每行国王掩码并约束相邻(八方向);行内合法掩码预处理,行间按约束转移;计数或方案最值。
概念解释
- 轮廓/占用掩码。
- 行间兼容约束。
原理流程
- 生成合法行状态。
- 行间判兼容。
- DP 累计方案。
代码 / 示例
国王:行内不相邻;行间列、对角不重叠
常见误区
- 误区:国王只判左右相邻;正解:八方向含对角。
- 误区:铺砖轮廓忘记延续;正解:未铺格子传给下一行。
追问
- Q:复杂度? A:O(rows·S²),S 合法行状态数。
- Q:状态能压到几维? A:只留上一行掩码可滚动。
02.7.2.3-009 状压 DP 与回溯枚举对比?
一句话结论
回溯枚举所有排列/组合不合并重复状态;状压 DP 把“已选集合”相同的分支合并,只保留该集合下最优值/计数;状态可压缩成掩码时 DP 避免指数重复枚举。
概念解释
- 合并状态:相同掩码等价。
- 回溯:保留路径分支。
原理流程
- 判断历史能否用集合表示。
- 可表示则状压 DP。
- 路径依赖强则回溯。
代码 / 图示
回溯:逐路径展开;状压:同集合状态合并
常见误区
- 误区:所有排列题都能状压;正解:顺序是解的一部分时不能合并。
- 误区:状压仍存完整路径;正解:只存掩码对应最优值。
追问
- Q:状压与记忆化关系? A:掩码即缓存键,状压 DP 是离散集合上的填表。
- Q:什么情况状压不如回溯? A:状态不可压缩或需输出全部路径。
02.7.2.3-010 dp 数组维度与规模怎么定?
一句话结论
状态为掩码时第一维 2ⁿ;若还需当前位置/行号,再加一维;按目标取最值或计数;n 较大时 2ⁿ 超内存,需评估规模或换方法。
概念解释
- 掩码维:2ⁿ。
- 附加维:位置/行。
原理流程
- 列状态维度。
- 估算 2ⁿ 规模。
- 选数组/滚动。
代码 / 示例
int[][] dp = new int[1 << n][n]; // TSP
常见误区
- 误区:n=20 以上仍开 2ⁿ 表;正解:内存不可行需换思路。
- 误区:漏掉附加位置维;正解:同集合不同位置状态不同。
追问
- Q:2²⁰ 状态多少? A:约百万级,附加维后需评估内存。
- Q:能滚动行维吗? A:行间 DP 只留上一行。
02.7.2.3-011 枚举子集转移怎么写?
一句话结论
转移到新掩码时枚举未选元素加入;反向枚举子集时 sub = (sub-1) & mask 遍历 mask 的所有子集;按题意子集作为上一状态或拆分方案。
概念解释
- 向前转移:加元素。
- 子集枚举:位运算递减。
原理流程
- 判断方向。
- 未选位循环或子集递减。
- 更新目标掩码。
代码 / 示例
for (int sub = mask; sub > 0; sub = (sub - 1) & mask) { ... }
常见误区
- 误区:子集枚举漏掉空集;正解:按题意包含 sub=0。
- 误区:新增元素重复计数;正解:每次只加一个未选位。
追问
- Q:子集枚举复杂度? A:一掩码下 2^k 子集。
- Q:分组背包状压用哪种? A:枚举组内子集合并。
02.7.2.3-012 合法状态怎么预处理?
一句话结论
先筛出行内/集合本身合法的掩码(无相邻、无冲突、大小限制),存入合法列表;DP 转移只在合法掩码间进行,减少无效枚举;预处理按题目约束判位运算。
概念解释
- 合法掩码:满足自身约束。
- 合法列表。
原理流程
- 遍历所有掩码。
- 位运算判合法性。
- 入列表供转移。
代码 / 示例
for (int m = 0; m < (1<<n); m++)
if ((m & (m<<1)) == 0) valid.add(m);
常见误区
- 误区:转移时才判非法;正解:预处理降低内层判断。
- 误区:合法条件遗漏;正解:列全行内约束。
追问
- Q:合法状态数远少于 2ⁿ 吗? A:约束强时显著减少。
- Q:预处理空间? A:O(2ⁿ) 存列表。
02.7.2.3-013 状压 DP 初始化怎么填?
一句话结论
空集掩码 0 按题意初始化:计数 dp[0]=1,最值 dp[0]=0 或按起点;不可达状态 INF/-INF;起点相关状态单独置初值;其余由转移填充。
概念解释
- 空集基准。
- 不可达哨兵。
原理流程
- 填空集/起点状态。
- 不可达给哨兵。
- 枚举掩码转移。
代码 / 示例
Arrays.fill(dp, INF); dp[1<<start][start] = 0;
常见误区
- 误区:最值全 0 初始化;正解:不可达用 INF。
- 误区:起点状态遗漏;正解:TSP 起点掩码单独置初值。
追问
- Q:计数 dp[0]? A:1 种空方案。
- Q:多起点怎么初始化? A:各起点状态分别置初值。
02.7.2.3-014 状压复杂度 O(2ⁿ·n²) 口径怎么报?
一句话结论
状态 2ⁿ,附加位置维 n,每状态枚举 n 个转移城市,时间 O(2ⁿ·n²);空间 O(2ⁿ·n);行型状压 O(rows·S²),S 合法行状态数;先数掩码状态再乘转移枚举。
概念解释
- 掩码状态:2ⁿ。
- 转移枚举:位置/子集数。
原理流程
- 数掩码与附加维。
- 乘单状态转移代价。
- 空间按表大小。
代码 / 示例
TSP:O(2ⁿ·n²);行放置:O(rows·S²)
常见误区
- 误区:状压复杂度只报 2ⁿ;正解:附加维与内层枚举要计入。
- 误区:空间忽略附加维;正解:TSP 表 2ⁿ·n。
追问
- Q:n=20 可行吗? A:2²⁰≈10⁶,附加维与转移需评估。
- Q:怎么降复杂度? A:合法状态筛选、滚动行维。
02.7.2.3-015 n 的上限怎么估算?
一句话结论
2ⁿ 状态量级决定上限:n=20 约百万,n=25 约三千三百万;附加维 n 与转移 n² 会进一步放大;面试题状压 n 一般 ≤20,超过需考虑其他算法或剪枝。
概念解释
- 指数状态。
- 规模红线。
原理流程
- 估算 2ⁿ。
- 乘附加维与转移。
- 判断是否可行。
代码 / 示例
2¹⁶≈6.5万;2²⁰≈105万;2²⁵≈3355万
常见误区
- 误区:n 大也硬上状压;正解:状态爆炸需换数学/贪心/网络流。
- 误区:只看掩码不看附加维;正解:总状态是掩码×附加维。
追问
- Q:n=30 状压可行吗? A:2³⁰ 不可行。
- Q:部分状态可达怎么办? A:记忆化只算可达掩码。
02.7.2.3-016 状压在排列/组合中是什么视角?
一句话结论
排列问题中掩码表示已选元素集合,配合当前位置做 DP 计数/最优;组合问题掩码表示选中子集;与回溯枚举相比,相同集合只保留一个最优状态,顺序是解的一部分时不可合并。
概念解释
- 集合视角。
- 顺序保留与否。
原理流程
- 掩码记已选。
- 未选元素转移。
- 同集合合并。
代码 / 示例
dp[mask]:已选集合 mask 的最优/计数
常见误区
- 误区:有序排列用集合合并;正解:顺序不同需保留路径,不能状压合并。
- 误区:掩码丢失元素顺序;正解:题目只关心集合时才可行。
追问
- Q:子集和计数能状压吗? A:状态是剩余和,不必掩码;元素集合视角另说。
- Q:状压适合求方案数吗? A:适合,计数累加即可。
02.7.2.3-017 集合等价与状态去重怎么理解?
一句话结论
两个分支到达相同掩码即同一集合状态,只需保留该状态下最优值/计数,不再区分到达路径;这是状压 DP 合并重复的依据;若路径本身影响合法性则不能合并。
概念解释
- 等价掩码。
- 合并保留最优。
原理流程
- 确认历史只影响集合。
- 同掩码状态合并。
- 保留最值/计数。
代码 / 示例
同 mask 不同路径 → 取最优 dp[mask]
常见误区
- 误区:路径顺序影响后续也合并;正解:状态不足时不能等价。
- 误区:计数合并重复;正解:方案数累加而非取最大。
追问
- Q:等价判据是什么? A:后续决策只依赖掩码。
- Q:怎么验证可合并? A:检查后续是否用得到达路径。
02.7.2.3-018 状压常见位运算错误有哪些?
一句话结论
高频错误:移除位用异或导致重复翻转、判位用错运算符、位移超宽度、相邻判断方向反、掩码初始与全集写错;统一用或置位、与非清位、与 1 判位,对照小规模掩码核对。
概念解释
- 置位/清位/判位。
- 位移边界。
原理流程
- 核对位运算语义。
- 小掩码打印二进制对照。
- 检查全集与边界。
代码 / 示例
置位 |;清位 &~;判位 &1;全集 (1<<n)-1
常见误区
- 误区:
mask ^ (1<<i)清位;正解:若位已为 1 会变回 1。 - 误区:全集写成 1<<n;正解:减 1 才是 n 位全 1。
追问
- Q:位编号从几开始? A:统一 0 起,避免错位。
- Q:负数掩码注意什么? A:整数高位符号位,别误用。
02.7.2.3-019 状压 DP 怎么调试?
一句话结论
先用 n 最小用例打印掩码二进制与 dp 值对照手算;检查合法掩码列表、初始化、转移前后掩码变化;定位是位运算错误、状态遗漏还是合并口径错误。
概念解释
- 小用例对照。
- 掩码可视化。
原理流程
- 最小 n 跑通。
- 打印掩码与 dp。
- 逐状态核对转移。
代码 / 示例
System.out.println(Integer.toBinaryString(mask));
常见误区
- 误区:直接上 n=10 调试;正解:先 n=2/3 验证位运算。
- 误区:只看最终最值不看中间状态;正解:逐掩码核对。
追问
- Q:状态不可达怎么查? A:检查初始化与转移是否覆盖。
- Q:计数偏大? A:重复转移或子集枚举重复。
02.7.2.3-020 状态压缩选型怎么判断?
一句话结论
状态本质是“哪些元素被选/占用”、n 较小、后续只依赖集合时用状压 DP;若顺序是解的一部分、n 很大或状态非集合类,则选回溯、线性 DP 或其他算法;先估 2ⁿ 是否可行。
概念解释
- 集合状态 + 小规模。
- 可行性估算。
原理流程
- 识别集合型状态。
- 估算 2ⁿ 规模。
- 排除顺序依赖后选用。
代码 / 图示
集合占用 + n≤20 → 状压;顺序依赖/规模大 → 其他
常见误区
- 误区:看到二元选择就状压;正解:先确认状态可压成集合。
- 误区:忽略 2ⁿ 规模;正解:超规模不可行。
追问
- Q:状压与数位 DP 区别? A:状压是集合掩码,数位是逐位数值约束。
- Q:状压能输出具体方案吗? A:记录前驱掩码回溯,否则只给最值/计数。