状压 DP

一、原理介绍

状态压缩动态规划（状压 DP） 是一种将集合或状态用二进制位进行压缩表示的动态规划方法。它适用于 维度较小（通常 n≤20）但需要记录多个元素“选/不选”或“存在/不存在”等信息的组合优化问题。

通过将每个元素映射到一个二进制位，可以用一个整数表示一个子集或状态，从而在 DP 中进行高效的转移。

常用位运算操作

操作 代码 含义
将第 $i$ 位设为 1 mask | (1 << i) 选中元素 i
将第 $i$ 位设为 0 mask & ~(1 << i) 移除元素 i
检查第 $i$ 位是否为 1 mask & (1 << i) 判断元素 i 是否存在
翻转第 $i$ 位 mask ^ (1 << i) 切换元素 i 的状态
检查是否有连续的 1 mask & (mask >> 1) 若结果为 0 则无相邻的 1（常用于棋盘问题）
去掉最低位的 1 mask & (mask - 1) lowbit 操作，常用于枚举子集

常见模型

  1. 棋盘/矩阵上的不相邻放置：每行状态用二进制表示放置位置，转移需满足本行无相邻、与上一行无上下相邻、且不与障碍冲突。
  2. 集合覆盖/选数问题：用一个整数表示已选取的集合，DP 逐步扩大集合，计算最小代价或最大收益。
  3. 排列/顺序相关的状压：dp[mask][i] 表示已走过的集合为 mask，最后停在 i 的最优值（如 TSP 问题）。
  4. 区间覆盖：用状压表示已使用的物品（如羊圈），转移时考虑用某个物品覆盖连续的一段，更新状态。

时间复杂度

通常为 O(n·2ⁿ) 或 O(n²·2ⁿ)，要求 n 一般不超过 20~22。

二、例题解析

例题1：宠物袋问题

题目描述
给定一个 N×M 的网格，某些格子有食物（不能放宠物）。宠物不能放在相邻（上下左右）的格子。求最多能放多少宠物。

输入格式
第一行 N, M（1≤M≤10，1≤N≤30）。接下来 N 行，每行 M 个数，1 表示该格有食物（不可用），0 表示空地。

输出格式
一个整数，表示最多可放的宠物数。
样例输入

1
2
3
2 3
1 0 0
1 1 1

样例输出

1
1

分析

由于 M 很小，我们可以用二进制表示每行的放置状态。

  • 用 row[i] 记录第 i 行的障碍情况：若第 j 列为 1，则第 j 位为 1（不可放置）。
  • 预处理所有行内无相邻宠物的状态：若 (state & (state >> 1)) == 0，则状态合法。
  • 定义 dp[i][state]：前 i 行，第 i 行状态为 state 时能放的最多宠物数。
  • 转移时，除了本行合法、不与障碍冲突，还需满足与上一行状态 pre 无上下相邻：state & pre == 0。
  • 边界：第一行直接初始化；最终答案为 max(dp[N-1][state])。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
n, m = map(int, input().split())
row = [0] * n
for i in range(n):
    a = list(map(int, input().split()))
    now_st = 0
    for j in range(m):
        if a[j] == 1:
            now_st |= (1 << j)   # 设置第j位为1
    row[i] = now_st
valid = [(i & (i >> 1)) == 0 for i in range(1 << m)]    #无连续1的有效状态
# 预处理每个状态中 1 的个数
count = [bin(i).count('1') for i in range(1 << m)]
dp = [[0] * (1 << m) for _ in range(n)]
for j in range(1 << m):
    if valid[j] and (j & row[0]) == 0:
        dp[0][j] = count[j]
# 逐行转移
for i in range(1, n):
    for j in range(1 << m):
        if valid[j] and (j & row[i]) == 0:
            for k in range(1 << m):
                if valid[k] and (k & j) == 0:
                    dp[i][j] = max(dp[i][j], dp[i - 1][k] + count[j])
print(max(dp[n - 1]))

例题2：羊圈问题

题目描述

有 m 头羊排成一列，第 i 头羊有 p_i 的概率逃跑。现有 n 种羊圈，第 i 种可以框住连续的 l_i 只羊，使其无法逃跑。羊圈不一定全部使用，也不一定按顺序使用。求合理安排羊圈后，能跑掉的羊的数量的期望的最小值。

输入格式

第一行 n, m。

第二行 n 个整数，表示每个羊圈可以覆盖的连续羊的数量 l1, l2, …, ln。

第三行 m 个浮点数，表示每头羊逃跑的概率 p1, p2, …, pm。

输出格式

一个浮点数，表示最小期望值（保留两位小数）。

样例输入

1
2
3
3 10
1 2 3
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0

样例输出

1
1.00

分析

羊圈的使用情况可以用一个 n 位的二进制数表示，第 k 位为 1 表示使用了第 k 种羊圈。

  • 状态定义：dp[i][mask] 表示处理完前 i 只羊，已经使用羊圈集合 mask 时，逃跑数量的最小期望。

  • 转移有两种：

    • 不放羊圈：第 i 只羊不被覆盖，逃跑概率贡献 p_i。即
      dp[i][mask] = dp[i-1][mask] + p_i

    • 放置某种羊圈：若 mask 中包含第 k 种羊圈，且该羊圈可以覆盖以 i 结尾的长度 l_k 的区间，则
      dp[i][mask] = min(dp[i][mask], dp[i - l_k]
      这表示用一个羊圈一口气覆盖了 [i - l_k + 1, i] 这些羊，它们都不会逃跑。

  • 最终答案为 dp[m][(1 << n) - 1]，即所有羊圈都被考虑后的最小值。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n, m = map(int, input().split())
num = list(map(int, input().split()))  # 每种羊圈的长度
p = [0] + list(map(float, input().split()))  # 每只羊的逃跑概率
# dp[i][j]：前 i 只羊，羊圈使用状态为 j 时的最小逃跑期望
dp = [[float('inf')]*(1<<n) for _ in range(m+1)]
dp[0][0]=0
for i in range(1,1<<n):
    dp[0][i]=0   
for i in range(1,m+1):
    for j in range(1<<n):
        # 不放羊圈
        dp[i][j]=dp[i-1][j]+p[i]
        # 尝试每种羊圈
        for k in range(n):
            if (j>>k)&1 and i-num[k]>= 0:
                pre=j&~(1<<k)
                dp[i][j] = min(dp[i][j],dp[i-num[k]][pre])
print('{:.2f}'.format(dp[m][(1 << n) - 1]))

三、解决状压 DP 的常用技巧

  1. 预处理合法状态
    很多问题（如棋盘放置）中，大量状态本身就不合法（例如有相邻 1），可以提前筛选并存储在数组中，减少无效枚举。

  2. 预处理状态间的转移关系
    对于每个合法状态，可预先找出所有能转移到它的前驱状态（如上一行状态），避免在 DP 循环中重复判断，大幅降低常数。

  3. 滚动数组优化空间
    状压 DP 的空间通常是 O(第一阶段大小 × 2ⁿ)，当第一阶段很大时（例如 N 很大但状态只依赖前一层），可用滚动数组将空间降为 O(2ⁿ)。

  4. 注意二进制位数
    通常 n 不超过 20，开数组时大小为 1 << n，勿混淆 n 与 m。Python 中注意 1 << n 可能很大，需结合题目内存限制。

  5. 边界与初始化
    设计 DP 状态时，通常起点为 dp[0][0] = 0，其他为 -∞ 或 +∞，确保未定义状态不会影响转移。

  6. 结合其他算法
    状压 DP 常与 图论、概率期望、排列组合 等结合，需要综合设计状态表示。

四、总结

状态压缩 DP 的核心在于用二进制位表达集合元素的存在性，从而在 O(2ⁿ) 的状态空间中进行最优子结构的递推。它小巧、精妙，是解决小规模组合优化问题的利器。

熟练位运算、预处理技巧以及常见模型（棋盘放置、集合覆盖、TSP 等）后，遇到类似问题便能快速构思出 DP 状态和转移方程。