状态压缩

一、什么是状态压缩？

状态压缩是利用二进制位来表示集合状态的技巧，多用于动态规划，简称状压DP。

把一组布尔状态（选/不选、占用/空闲、存在/不存在）压缩成一个整数，整数的每一个二进制位代表一个状态：

• 位为 1：代表选中、占用、存在
• 位为 0：代表不选、空闲、不存在

例如数字 5，二进制 101，表示第0位、第2位有效，第1位无效。

核心思想：用一个整数代替数组来记录状态，大幅压缩空间，方便位运算快速转移。 一般数据范围 n ≤ 20，2^20 约一百万，是状压常见上限；n超过20一般不适合暴力状压。

二、适用场景

题目出现下面特征优先考虑状态压缩：

• n很小，一般 n ≤ 20
• 每个元素只有两种状态：选或者不选
• 集合、子集、排列、棋盘摆放、互不冲突选择
• DP状态需要记录一组元素的选择情况

三、状态压缩常用位运算格式（必背）

假设状态记为 mask，i代表第i个位置（从0开始）

// 1. 将第 i 位 设置为 1（选中i）
mask | (1 << i)

// 2. 将第 i 位 设置为 0（取消i）
mask & ~(1 << i)

// 3. 判断第 i 位 是否为1（是否选中i）
(mask & (1 << i)) != 0

// 4. 翻转第 i 位
mask ^ (1 << i)

// 5. 获取mask二进制中1的个数
Integer.bitCount(mask)

// 6. 遍历mask所有子集
int sub = mask;
do {
    sub = (sub - 1) & mask;
} while (sub != mask);

// 7. 枚举全部状态：0 ~ (1 << n) -1
for(int mask = 0; mask < (1 << n); mask++){}

// 8. 判断两个状态是否冲突（没有重叠1）
(maskA & maskB) == 0

运算符简单说明

• <<：左移，1 << i 等于2的i次方
• |：按位或，置1
• &：按位与，检测位、清零
• ~：按位取反
• ^：异或，翻转位

四、状压DP通用模板

// n个元素，dp[mask]代表mask状态下最优值
int n = ...;
int[][] dp = new int[1 << n][...];

// 初始化
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;

// 枚举所有状态
for(int mask = 0; mask < (1 << n); mask++){
    // 当前状态mask，尝试选下一个i
    for(int i = 0; i < n; i++){
        // 如果i没有被选过
        if( (mask & (1 << i)) == 0 ){
            int nextMask = mask | (1 << i);
            // 状态转移
            dp[nextMask] = Math.min(dp[nextMask], dp[mask] + cost(mask,i));
        }
    }
}
// 全选状态 (1<<n)-1
return dp[(1 << n)-1];

五、高频经典例题

1. 旅行商TSP（LeetCode 943 相似，经典TSP模板）

题目：n个城市，从起点出发每个城市恰好走一次，求最小花费。n ≤ 12。 dp[mask][u]：mask代表已经走过的城市集合，u代表当前停留在u城市。

public int tsp(int[][] graph, int n){
    int INF = 0x3f3f3f3f;
    int[][] dp = new int[1 << n][n];
    for(int[] arr : dp) Arrays.fill(arr, INF);
    dp[1 << 0][0] = 0;

    for(int mask = 0; mask < (1 << n); mask++){
        for(int u = 0; u < n; u++){
            if(dp[mask][u] == INF) continue;
            // 去往还没访问过的v
            for(int v = 0; v < n; v++){
                if( (mask & (1 << v)) != 0 ) continue;
                int nextMask = mask | (1 << v);
                dp[nextMask][v] = Math.min(dp[nextMask][v], dp[mask][u] + graph[u][v]);
            }
        }
    }
    int full = (1 << n) - 1;
    int ans = INF;
    for(int i = 0; i < n; i++){
        ans = Math.min(ans, dp[full][i]);
    }
    return ans;
}

2. 子集枚举模板（获取mask全部子集）

// 遍历mask所有非空子集
int sub = mask;
do {
    sub = (sub - 1) & mask;
    // 处理sub子集
} while(sub != mask);

六、状态压缩优缺点（面试口述）

1. 优点

• 使用整数代替数组存储状态，空间开销小
• 位运算速度极快，方便子集、冲突判断
• 可以处理n较小的集合选择DP问题

2. 缺点

• 复杂度 O(2^n)，n>20会直接超时
• 二进制可读性差，调试难度偏高

七、总结

1. 状态压缩 = 二进制位表示集合状态 + DP，适合n≤20场景
2. mask为状态整数，每一位代表一个元素选或不选
3. 核心操作：置位、清零、检测位、统计1的个数、子集枚举
4. 经典模型：TSP旅行商、棋盘摆放、子集DP
5. 时间复杂度 O(2^n * n)，n一旦变大就不能使用状压

总结

• 状态压缩：借助二进制整数压缩集合状态，配合位运算做DP状态转移。
• 核心：mask记录选择集合，位运算完成状态变更与校验。
• 限制条件：n一般不超过20，指数级复杂度。
• 高频套路：枚举mask所有状态，再尝试添加新元素生成nextMask做转移。