状压DP-基本框架

- 一、状压DP的核心思想与适用场景
- - 1.1 问题特征
  - 1.2 核心思想
  - 1.3 与传统DP的对比
- 二、位运算基础：状压DP的语法
- 三、状压DP的基本框架
- - 3.1 步骤拆解
  - 3.2 通用代码模板
- 四、经典案例详解
- - 4.1 旅行商问题（TSP）
  - - 问题描述
    - 状压DP设计
    - 代码实现
  - 4.2 集合覆盖问题（最小代价覆盖所有元素）
  - - 问题描述
    - 状压DP设计
    - 代码实现
- 五、状压DP的优化技巧
- - 5.1 状态剪枝
  - 5.2 位运算优化
  - 5.3 空间优化
  - 总结

状态压缩动态规划（Bitmask DP）是解决“小规模集合选择”问题的高效方法，当问题涉及对有限元素的子集进行状态描述时，传统DP的多维状态会导致空间爆炸，而状压DP通过二进制位表示集合状态，将高维状态压缩为一个整数，显著降低空间复杂度。

一、状压DP的核心思想与适用场景

1.1 问题特征

状压DP适用于以下场景：

元素数量少：通常n≤20（二进制状态需要2^n个，n=20对应约百万级状态，可接受）。
状态与子集相关：问题的解依赖于“哪些元素被选中”或“元素的选择顺序”（如旅行商问题中已访问的城市集合）。
子集状态可转移：从一个子集状态可通过添加/删除元素过渡到另一个状态（如从“选中{0,1}”到“选中{0,1,2}”）。

1.2 核心思想

状态压缩：用一个整数（二进制数）表示元素的选择状态。例如，n=3时：
- 二进制101（十进制5）表示选中第0和第2个元素（从右往左数，低位对应下标0）；
- 二进制000表示未选中任何元素。
DP状态定义：dp[mask]表示“在状态mask下的最优解”（如最小代价、最大价值等），其中mask是压缩后的二进制状态。
状态转移：通过枚举mask中未选中的元素，生成新状态mask | (1 << i)，并更新dp[new_mask]。

1.3 与传统DP的对比

维度	传统DP（如背包问题）	状压DP
状态表示	多维数组（如`dp[i][j]`）	单整数`mask`（压缩子集）
适用规模	元素数量大（`n≤1e5`）	元素数量小（`n≤20`）
核心技巧	空间优化（如滚动数组）	位运算操作（状态转换）
典型问题	0/1背包、最长上升子序列	旅行商问题、集合覆盖问题

二、位运算基础：状压DP的语法

状压DP依赖二进制位运算实现状态操作，核心运算如下：

操作	含义	位运算表达式
检查元素`i`是否选中	第`i`位是否为1	`(mask & (1 << i)) != 0`
选中元素`i`	将第`i`位设为1	`mask
取消选中元素`i`	将第`i`位设为0	`mask & ~(1 << i)`
切换元素`i`的状态	第`i`位0变1，1变0	`mask ^ (1 << i)`
统计选中元素数量	二进制中1的个数（popcount）	`Integer.bitCount(mask)`
清空所有元素	状态置为0	`mask = 0`

示例：mask = 5（二进制101）：

检查元素1是否选中：5 & (1<<1) = 101 & 010 = 000 → 未选中；
选中元素1：5 | (1<<1) = 101 | 010 = 111 → 新状态7；
统计选中数量：Integer.bitCount(5) = 2。

三、状压DP的基本框架

3.1 步骤拆解

确定状态表示：用mask表示元素的选择状态，定义dp[mask]的具体含义（如代价、价值）。
初始化：设置初始状态的dp值（如dp[0] = 0表示未选任何元素时的初始代价）。
状态转移：
- 遍历所有可能的mask（从0到2^n - 1）；
- 对每个mask，枚举可添加的元素i（未被mask选中）；
- 计算新状态new_mask = mask | (1 << i)，更新dp[new_mask]。
结果提取：根据问题目标，返回dp[full_mask]（full_mask = (1 << n) - 1表示所有元素都被选中）或其他特定状态的值。

3.2 通用代码模板

public class BitmaskDPTemplate {int n; // 元素数量int[] dp; // dp[mask]表示状态mask下的最优解public BitmaskDPTemplate(int n) {this.n = n;int size = 1 << n; // 状态总数：2^ndp = new int[size];// 初始化：除初始状态外均设为无穷大（求最小值时）或负无穷（求最大值时）Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0; // 初始状态：未选任何元素}public int solve() {int fullMask = (1 << n) - 1; // 所有元素都被选中的状态// 遍历所有状态for (int mask = 0; mask < (1 << n); mask++) {if (dp[mask] == Integer.MAX_VALUE) continue; // 跳过不可达状态// 枚举可添加的元素ifor (int i = 0; i < n; i++) {if ((mask & (1 << i)) != 0) continue; // 元素i已被选中，跳过int newMask = mask | (1 << i); // 选中元素i后的新状态// 计算新状态的代价（根据具体问题修改）int cost = calculateCost(mask, i);dp[newMask] = Math.min(dp[newMask], dp[mask] + cost);}}return dp[fullMask]; // 返回所有元素被选中时的最优解}// 根据具体问题计算从mask添加元素i的代价private int calculateCost(int mask, int i) {// 示例：代价为i+1（实际需根据问题定义）return i + 1;}public static void main(String[] args) {BitmaskDPTemplate solver = new BitmaskDPTemplate(3); // 3个元素System.out.println(solver.solve()); // 输出0+1+2+3=6（示例逻辑）}
}

四、经典案例详解

4.1 旅行商问题（TSP）

问题描述

给定n个城市和两两之间的距离，求从起点出发，访问所有城市恰好一次并返回起点的最短路径。

示例：n=4，距离矩阵dist[i][j]表示城市i到j的距离，求最短回路。

状压DP设计

状态定义：dp[mask][u]表示“已访问的城市集合为mask，当前在城市u时的最短距离”。
（注：此处状态包含mask和当前城市u，是二维状压DP）
状态转移：
- 初始状态：dp[1 << start][start] = 0（仅访问起点，距离为0）。
- 对每个mask和当前城市u，枚举未访问的城市v，则：
  dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], dp[mask][u] + dist[u][v])。
结果计算：访问所有城市后返回起点，总距离为min(dp[full_mask][u] + dist[u][start])（u为最后一个城市）。

代码实现

import java.util.*;public class TSP {int n;int[][] dist; // 距离矩阵int[][] dp; // dp[mask][u]: 状态mask下当前在u的最短距离final int INF = 1 << 30;public TSP(int n, int[][] dist) {this.n = n;this.dist = dist;int size = 1 << n;dp = new int[size][n];// 初始化：所有状态设为无穷大for (int i = 0; i < size; i++) {Arrays.fill(dp[i], INF);}// 起点设为0，初始状态：仅访问0dp[1 << 0][0] = 0;}public int shortestPath() {int fullMask = (1 << n) - 1;// 遍历所有状态for (int mask = 0; mask < (1 << n); mask++) {// 遍历当前所在城市ufor (int u = 0; u < n; u++) {if ((mask & (1 << u)) == 0) continue; // u不在mask中，跳过if (dp[mask][u] == INF) continue; // 状态不可达// 枚举未访问的城市vfor (int v = 0; v < n; v++) {if ((mask & (1 << v)) != 0) continue; // v已访问，跳过int newMask = mask | (1 << v);// 更新新状态的距离if (dp[newMask][v] > dp[mask][u] + dist[u][v]) {dp[newMask][v] = dp[mask][u] + dist[u][v];}}}}// 计算返回起点的总距离int result = INF;for (int u = 0; u < n; u++) {if (u == 0) continue; // 起点无需返回result = Math.min(result, dp[fullMask][u] + dist[u][0]);}return result;}public static void main(String[] args) {// 示例：4个城市的距离矩阵int n = 4;int[][] dist = {{0, 1, 2, 3},{1, 0, 4, 5},{2, 4, 0, 6},{3, 5, 6, 0}};TSP tsp = new TSP(n, dist);System.out.println(tsp.shortestPath()); // 输出1+4+6+3=14（示例路径：0→1→2→3→0）}
}

4.2 集合覆盖问题（最小代价覆盖所有元素）

问题描述

给定n个元素和m个子集，每个子集S_i有代价c_i，求代价最小的子集组合，使其覆盖所有n个元素。

示例：n=3，子集S_0={0,1}（代价2），S_1={1,2}（代价3），S_2={0,2}（代价4），最优解为S_0 + S_1（代价5，覆盖{0,1,2}）。

状压DP设计

状态定义：dp[mask]表示“覆盖元素集合为mask时的最小代价”。
状态转移：
- 初始状态：dp[0] = 0（覆盖空集代价0）。
- 对每个mask和每个子集S_i，新覆盖的集合为new_mask = mask | S_i_mask（S_i_mask是子集S_i的二进制表示），则：
  dp[new_mask] = min(dp[new_mask], dp[mask] + c_i)。
结果提取：dp[full_mask]（full_mask = (1 << n) - 1）。

代码实现

import java.util.*;public class SetCover {int n; // 元素总数int m; // 子集数量int[] subsetMask; // 每个子集的二进制表示int[] cost; // 每个子集的代价int[] dp; // dp[mask]: 覆盖mask集合的最小代价final int INF = 1 << 30;public SetCover(int n, int m, int[] subsetMask, int[] cost) {this.n = n;this.m = m;this.subsetMask = subsetMask;this.cost = cost;int size = 1 << n;dp = new int[size];Arrays.fill(dp, INF);dp[0] = 0; // 初始状态}public int minTotalCost() {int fullMask = (1 << n) - 1;// 遍历所有状态for (int mask = 0; mask < (1 << n); mask++) {if (dp[mask] == INF) continue;// 枚举每个子集for (int i = 0; i < m; i++) {int newMask = mask | subsetMask[i];// 更新新状态的代价if (dp[newMask] > dp[mask] + cost[i]) {dp[newMask] = dp[mask] + cost[i];}}}return dp[fullMask];}public static void main(String[] args) {int n = 3; // 元素0,1,2int m = 3; // 3个子集int[] subsetMask = {0b110, // S0: {1,2}（二进制从右数，0b110表示第1和2位为1）0b101, // S1: {0,2}0b011  // S2: {0,1}};int[] cost = {2, 3, 4};SetCover solver = new SetCover(n, m, subsetMask, cost);System.out.println(solver.minTotalCost()); // 输出2+3=5（S0覆盖1,2，S1覆盖0）}
}