罗罗编程学习记录
本页内容 展开查看

02.7.2.3 状态压缩 DP

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.7 动态规划 / 02.7.2 区间树形与状态压缩 DP

02.7.2.3-001 状态压缩的思想是什么?

一句话结论

当状态是一组元素的选取/占用集合时,用整数二进制位掩码表示集合:位 1 表示选中;把集合维度压缩成一个整数下标,存入 DP 表;适合 n 较小(通常 ≤20)的集合类问题。

概念解释

  • 掩码:位集合。
  • 压缩:集合 → 整数。

原理流程

  1. 把每个元素对应一位。
  2. 位运算表达集合操作。
  3. 掩码作 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。
  • 集合运算:位运算。

原理流程

  1. 置位/清位/判位。
  2. 集合交并差用位与或非。
  3. 空集为 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 的位置。
  • 子集枚举:位运算遍历。

原理流程

  1. 找未选元素 i。
  2. 新掩码 mask | (1<<i)。
  3. 更新目标状态。

代码 / 示例

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)。

原理流程

  1. 按需求选位运算。
  2. 避免循环判位。
  3. 掩码合法性预处理。

代码 / 示例

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²)。

概念解释

  • 状态:已访问集合 + 当前位置。
  • 末步:下一城市。

原理流程

  1. 初始化起点状态。
  2. 枚举掩码与当前城市。
  3. 扩展未访问城市。

代码 / 示例

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 是回路,终态还要加回起点距离;状态转移框架相同,仅终点口径不同。

概念解释

  • 路径:终点不回起点。
  • 回路:终点回起点。

原理流程

  1. 同 TSP 填表。
  2. 路径取全选各城市最小。
  3. 回路加返程距离。

代码 / 示例

路径: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 行该放置方案的最优/计数;逐行转移。

概念解释

  • 行掩码:本行占用列。
  • 行间约束:列不重叠。

原理流程

  1. 预处理合法行掩码。
  2. 逐行枚举上一行兼容掩码。
  3. 转移累加/取优。

代码 / 示例

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 棋盘铺地砖/放国王怎么状压?

一句话结论

铺砖按行轮廓掩码记录已被上一行砖占用的格子;放国王记录每行国王掩码并约束相邻(八方向);行内合法掩码预处理,行间按约束转移;计数或方案最值。

概念解释

  • 轮廓/占用掩码。
  • 行间兼容约束。

原理流程

  1. 生成合法行状态。
  2. 行间判兼容。
  3. DP 累计方案。

代码 / 示例

国王:行内不相邻;行间列、对角不重叠

常见误区

  • 误区:国王只判左右相邻;正解:八方向含对角。
  • 误区:铺砖轮廓忘记延续;正解:未铺格子传给下一行。

追问

  • Q:复杂度? A:O(rows·S²),S 合法行状态数。
  • Q:状态能压到几维? A:只留上一行掩码可滚动。

02.7.2.3-009 状压 DP 与回溯枚举对比?

一句话结论

回溯枚举所有排列/组合不合并重复状态;状压 DP 把“已选集合”相同的分支合并,只保留该集合下最优值/计数;状态可压缩成掩码时 DP 避免指数重复枚举。

概念解释

  • 合并状态:相同掩码等价。
  • 回溯:保留路径分支。

原理流程

  1. 判断历史能否用集合表示。
  2. 可表示则状压 DP。
  3. 路径依赖强则回溯。

代码 / 图示

回溯:逐路径展开;状压:同集合状态合并

常见误区

  • 误区:所有排列题都能状压;正解:顺序是解的一部分时不能合并。
  • 误区:状压仍存完整路径;正解:只存掩码对应最优值。

追问

  • Q:状压与记忆化关系? A:掩码即缓存键,状压 DP 是离散集合上的填表。
  • Q:什么情况状压不如回溯? A:状态不可压缩或需输出全部路径。

02.7.2.3-010 dp 数组维度与规模怎么定?

一句话结论

状态为掩码时第一维 2ⁿ;若还需当前位置/行号,再加一维;按目标取最值或计数;n 较大时 2ⁿ 超内存,需评估规模或换方法。

概念解释

  • 掩码维:2ⁿ。
  • 附加维:位置/行。

原理流程

  1. 列状态维度。
  2. 估算 2ⁿ 规模。
  3. 选数组/滚动。

代码 / 示例

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 的所有子集;按题意子集作为上一状态或拆分方案。

概念解释

  • 向前转移:加元素。
  • 子集枚举:位运算递减。

原理流程

  1. 判断方向。
  2. 未选位循环或子集递减。
  3. 更新目标掩码。

代码 / 示例

for (int sub = mask; sub > 0; sub = (sub - 1) & mask) { ... }

常见误区

  • 误区:子集枚举漏掉空集;正解:按题意包含 sub=0。
  • 误区:新增元素重复计数;正解:每次只加一个未选位。

追问

  • Q:子集枚举复杂度? A:一掩码下 2^k 子集。
  • Q:分组背包状压用哪种? A:枚举组内子集合并。

02.7.2.3-012 合法状态怎么预处理?

一句话结论

先筛出行内/集合本身合法的掩码(无相邻、无冲突、大小限制),存入合法列表;DP 转移只在合法掩码间进行,减少无效枚举;预处理按题目约束判位运算。

概念解释

  • 合法掩码:满足自身约束。
  • 合法列表。

原理流程

  1. 遍历所有掩码。
  2. 位运算判合法性。
  3. 入列表供转移。

代码 / 示例

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;起点相关状态单独置初值;其余由转移填充。

概念解释

  • 空集基准。
  • 不可达哨兵。

原理流程

  1. 填空集/起点状态。
  2. 不可达给哨兵。
  3. 枚举掩码转移。

代码 / 示例

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ⁿ。
  • 转移枚举:位置/子集数。

原理流程

  1. 数掩码与附加维。
  2. 乘单状态转移代价。
  3. 空间按表大小。

代码 / 示例

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,超过需考虑其他算法或剪枝。

概念解释

  • 指数状态。
  • 规模红线。

原理流程

  1. 估算 2ⁿ。
  2. 乘附加维与转移。
  3. 判断是否可行。

代码 / 示例

2¹⁶≈6.5万;2²⁰≈105万;2²⁵≈3355万

常见误区

  • 误区:n 大也硬上状压;正解:状态爆炸需换数学/贪心/网络流。
  • 误区:只看掩码不看附加维;正解:总状态是掩码×附加维。

追问

  • Q:n=30 状压可行吗? A:2³⁰ 不可行。
  • Q:部分状态可达怎么办? A:记忆化只算可达掩码。

02.7.2.3-016 状压在排列/组合中是什么视角?

一句话结论

排列问题中掩码表示已选元素集合,配合当前位置做 DP 计数/最优;组合问题掩码表示选中子集;与回溯枚举相比,相同集合只保留一个最优状态,顺序是解的一部分时不可合并。

概念解释

  • 集合视角。
  • 顺序保留与否。

原理流程

  1. 掩码记已选。
  2. 未选元素转移。
  3. 同集合合并。

代码 / 示例

dp[mask]:已选集合 mask 的最优/计数

常见误区

  • 误区:有序排列用集合合并;正解:顺序不同需保留路径,不能状压合并。
  • 误区:掩码丢失元素顺序;正解:题目只关心集合时才可行。

追问

  • Q:子集和计数能状压吗? A:状态是剩余和,不必掩码;元素集合视角另说。
  • Q:状压适合求方案数吗? A:适合,计数累加即可。

02.7.2.3-017 集合等价与状态去重怎么理解?

一句话结论

两个分支到达相同掩码即同一集合状态,只需保留该状态下最优值/计数,不再区分到达路径;这是状压 DP 合并重复的依据;若路径本身影响合法性则不能合并。

概念解释

  • 等价掩码。
  • 合并保留最优。

原理流程

  1. 确认历史只影响集合。
  2. 同掩码状态合并。
  3. 保留最值/计数。

代码 / 示例

同 mask 不同路径 → 取最优 dp[mask]

常见误区

  • 误区:路径顺序影响后续也合并;正解:状态不足时不能等价。
  • 误区:计数合并重复;正解:方案数累加而非取最大。

追问

  • Q:等价判据是什么? A:后续决策只依赖掩码。
  • Q:怎么验证可合并? A:检查后续是否用得到达路径。

02.7.2.3-018 状压常见位运算错误有哪些?

一句话结论

高频错误:移除位用异或导致重复翻转、判位用错运算符、位移超宽度、相邻判断方向反、掩码初始与全集写错;统一用或置位、与非清位、与 1 判位,对照小规模掩码核对。

概念解释

  • 置位/清位/判位。
  • 位移边界。

原理流程

  1. 核对位运算语义。
  2. 小掩码打印二进制对照。
  3. 检查全集与边界。

代码 / 示例

置位 |;清位 &~;判位 &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 值对照手算;检查合法掩码列表、初始化、转移前后掩码变化;定位是位运算错误、状态遗漏还是合并口径错误。

概念解释

  • 小用例对照。
  • 掩码可视化。

原理流程

  1. 最小 n 跑通。
  2. 打印掩码与 dp。
  3. 逐状态核对转移。

代码 / 示例

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ⁿ 是否可行。

概念解释

  • 集合状态 + 小规模。
  • 可行性估算。

原理流程

  1. 识别集合型状态。
  2. 估算 2ⁿ 规模。
  3. 排除顺序依赖后选用。

代码 / 图示

集合占用 + n≤20 → 状压;顺序依赖/规模大 → 其他

常见误区

  • 误区:看到二元选择就状压;正解:先确认状态可压成集合。
  • 误区:忽略 2ⁿ 规模;正解:超规模不可行。

追问

  • Q:状压与数位 DP 区别? A:状压是集合掩码,数位是逐位数值约束。
  • Q:状压能输出具体方案吗? A:记录前驱掩码回溯,否则只给最值/计数。