状态压缩指的是通过一串0-1码保存一个集合的状态，把一个集合压缩成一个整数。例如，有一行棋子，它们的排列分别是：黑 白 白 黑 黑 白 黑 白 ，这就可以用10011010(2)来表示这个状态。
在线性DP中，动态规划的过程随着“阶段”的增长，在每个状态维度上不断扩展的。在任意时刻，已经求出最优解的状态和尚未求出最优解的状态在各个维度上的分界点组成了DP扩展的“轮廓”。对于某些问题，我们需要在动态规划的“状态”中记录一个集合，保存这个“轮廓”的详细信息，以便进行状态转移。若集合大小不超过N，集合中每个元素都是小于K的自然数，则我们可以把这个集合看作一个N位的K进制数，以一个[0，KN-1]之间的十进制整数的形式作为DP状态的一维，这种把集合转化为整数记录在DP状态种的一类算法，被称为状态压缩动态规划算法。
状态压缩DP的核心思想是使用整数的二进制表示来表示复杂的状态集合。每一个比特位可以代表一个元素的某种状态（通常是存在或缺失）。这样，一个整数可以存储多个独立状态的信息，使得状态的转移和查询都非常高效。
状压DP中常用位运算的几个小技巧:
1. 判断 x 是否是奇数
方法: if(x&1)，如果x在2进制下的最后一位是1，说明是奇数。
2. 判断 x 是 2 的幂
方法: if(x&(x-1)==0)，如果x是2的幂，也就是最高位是1，其余为是0，那么 x&(x-1) 一定是0 (比如：100&011=0)。
3. 判断一个数字 x 二进制下第 i 位是不是等于 1。(最低第1位)
方法: if((1<<(i-1))&x)，将1左移i-1位，相当于制造了一个只有第 i 位上是 1，其他位上都是 0 的二进制数。然后与 x 做与运算，如果结果>0，说明 x 第 i 位上是1, 反之则是 0。
4. 将一个数字 x 二进制下第 i 位更改成 1
方法: x= x|(1<<(i-1))
5. 将一个数字 x 二进制下第 i 位更改成 0
方法: x=x&~(1<<(i-1))
6. 判断数字 x 二进制下是否有相邻的 1
方法: if(x&(x<<1))