状压DP(Bit mask DP)将状态压缩为二进制表示，用于处理状态复杂的问题。主要分为一维和二维两种类型。
一维状压DP
最经典的是求最短哈密顿路径，对应 \(n\) 个结点的带权无向图，暴力枚举所有情况的时间复杂度为 \(O(n)\)，但是我们思考一下，到达某个顶点时，需要记录在这之前已经走过结点是哪些，但无需记录走的顺序，可以用一个二进制数表示当前状态，其中为\(1\)的下标表示已经走过的结点，这样就只需枚举 \(2^n-1\) 种状态，同时枚举上一个结点和当前结点进行状态更新，这样时间复杂度可降为 \(O(n^2 2^n)\)。
例题：
最短Hamilton路径
Shuffling Songs
二维状压DP
这种类型通常给定一个二维数组，一行的状态可以用一个二进制数表示，从上到下依次转移下来，此类题目一般需要注意从i开始循环防止越界，最后多循环一次方便输出答案，当二维数组的行和列维度不同时，当行列顺序无影响时，可以通过交换枚举顺序控制算法的时间复杂度。
标签：状态,结点,复杂度,状压,枚举,DP From： https://www.cnblogs.com/catting123/p/18337234