状压 DP
简介
状压 DP 是动态规划的一种，通过将状态集合转化为整数记录在 DP 状态中来实现状态转移的目的．
为了达到更低的时间复杂度，通常需要寻找更低状态数的状态．大部分题目中会利用二元状态，用 𝑛n
位二进制数表示 𝑛n 个独立二元状态的情况．
使用状态压缩通常涉及位操作，关于基础位操作详见 位操作 页面．
例题 1
在 𝑁 ×𝑁N×N 的棋盘里面放 𝐾K 个国王（1 ≤𝑁 ≤9,1 ≤𝐾 ≤𝑁 ×𝑁1≤N≤9,1≤K≤N×N），使他们互不攻击，共有多少种摆放方案．
国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 88 个格子．
解释
设 𝑓(𝑖,𝑗,𝑙)f(i,j,l) 表示前 𝑖i 行，第 𝑖i 行的状态为 𝑗j，且棋盘上已经放置 𝑙l 个国王时的合法方案数．
对于编号为 𝑗j 的状态，我们用二进制整数 𝑠𝑖𝑡(𝑗)sit(j) 表示国王的放置情况，𝑠𝑖𝑡(𝑗)sit(j) 的某个二进制位为 00 表示对应位置不放国王，为 11 表示在对应位置上放置国王；用 𝑠𝑡𝑎(𝑗)sta(j) 表示该状态的国王个数，即二进制数 𝑠𝑖𝑡(𝑗)sit(j) 中 11 的个数．例如，如下图所示的状态可用二进制数 100101100101 来表示（棋盘左边对应二进制低位），则有 𝑠𝑖𝑡(𝑗) =100101(2) =37,𝑠𝑡𝑎(𝑗) =3sit(j)=100101(2)=37,sta(j)=3．
设当前行的状态为 𝑗j，上一行的状态为 𝑥x，可以得到下面的状态转移方程：𝑓(𝑖,𝑗,𝑙) =∑𝑓(𝑖 −1,𝑥,𝑙 −𝑠𝑡𝑎(𝑗))f(i,j,l)=∑f(i−1,x,l−sta(j))．
设上一行的状态编号为 𝑥x，在保证当前行和上一行不冲突的前提下，枚举所有可能的 𝑥x 进行转移，转移方程：
𝑓(𝑖,𝑗,𝑙)=∑𝑓(𝑖−1,𝑥,𝑙−𝑠𝑡𝑎(𝑗))f(i,j,l)=∑f(i−1,x,l−sta(j))
实现
参考代码
---|---
## 例题 2
[[POI2004] PRZ](https://www.luogu.com.cn/problem/P5911)
有 𝑛n 个人需要过桥，第 𝑖i 的人的重量为 𝑤𝑖wi，过桥用时为 𝑡𝑖ti. 这些人过桥时会分成若干组，只有在某一组的所有人全部过桥后，其余的组才能过桥．桥最大承重为 𝑊W，问这些人全部过桥的最短时间．
100 ≤𝑊 ≤400100≤W≤400，1 ≤𝑛 ≤161≤n≤16，1 ≤𝑡𝑖 ≤501≤ti≤50，10 ≤𝑤𝑖 ≤10010≤wi≤100.
### 解释
我们用 𝑆S 表示所有人构成集合的一个子集，设 𝑡(𝑆)t(S) 表示 𝑆S 中人的最长过桥时间，𝑤(𝑆)w(S) 表示 𝑆S 中所有人的总重量，𝑓(𝑆)f(S) 表示 𝑆S 中所有人全部过桥的最短时间，则：
{𝑓(∅)=0,𝑓(𝑆)=min𝑇⊆𝑆; 𝑤(𝑇)≤𝑊{𝑡(𝑇)+𝑓(𝑆∖𝑇)}.{f(∅)=0,f(S)=minT⊆S; w(T)≤W{t(T)+f(S∖T)}.
需要注意的是这里不能直接枚举集合再判断是否为子集，而应使用 [子集枚举](../../math/binary-set/#遍历所有掩码的子掩码)，从而使时间复杂度为 𝑂(3𝑛)O(3n).
### 实现
参考代码
---|---
习题
本页面最近更新： 2026/1/27 12:26:08，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：StudyingFather, Ir1d, H-J-Granger, NachtgeistW, countercurrent-time, Enter-tainer, ouuan, Marcythm, sshwy, Tiphereth-A, AngelKitty, c-forrest, CCXXXI, cjsoft, diauweb, Early0v0, ezoixx130, GekkaSaori, Henry-ZHR, HeRaNO, Konano, LovelyBuggies, Makkiy, mgt, minghu6, P-Y-Y, PotassiumWings, SamZhangQingChuan, Suyun514, weiyong1024, chieh2lu2, Chrogeek, GavinZhengOI, Gesrua, hhc0001, hsfzLZH1, iamtwz, kenlig, ksyx, kxccc, Link-cute, lychees, Peanut-Tang, REYwmp, shinzanmono, SukkaW, TianKong-y, TOMWT-qwq, Xeonacid, YuJunDongGit, zhb2000 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用