狀態(tài)壓縮DP一般是基于二進制進行的。

狀態(tài)壓縮DP一般分為兩類：

①基于連通性DP（棋盤式）

②集合式（表示每一個元素是否在集合中）

一、概述

1. 狀態(tài)壓縮

狀態(tài)壓縮就是使用某種方法，簡明扼要地以最小代價來表示某種狀態(tài)，通常是用一串01數(shù)字（二進制數(shù)）來表示各個點的狀態(tài)。這就要求使用狀態(tài)壓縮的對象的點的狀態(tài)必須只有兩種，0 或 1；當然如果有三種狀態(tài)用三進制來表示也未嘗不可。

2. 使用條件

從狀態(tài)壓縮的特點來看，這個算法適用的題目符合以下的條件：

解法需要保存一定的狀態(tài)數(shù)據(jù)（表示一種狀態(tài)的一個數(shù)據(jù)值），每個狀態(tài)數(shù)據(jù)通常情況下是可以通過2進制來表示的。這就要求狀態(tài)數(shù)據(jù)的每個單元只有兩種狀態(tài)，比如說棋盤上的格子，放棋子或者不放，或者是硬幣的正反兩面。這樣用0或者1來表示狀態(tài)數(shù)據(jù)的每個單元，而整個狀態(tài)數(shù)據(jù)就是一個一串0和1組成的二進制數(shù)。

解法需要將狀態(tài)數(shù)據(jù)實現(xiàn)為一個基本數(shù)據(jù)類型，比如int，long等等，即所謂的狀態(tài)壓縮。狀態(tài)壓縮的目的一方面是縮小了數(shù)據(jù)存儲的空間，另一方面是在狀態(tài)對比和狀態(tài)整體處理時能夠提高效率。這樣就要求狀態(tài)數(shù)據(jù)中的單元個數(shù)不能太大，比如用int來表示一個狀態(tài)的時候，狀態(tài)的單元個數(shù)不能超過32（32位的機器），所以題目一般都是至少有一維的數(shù)據(jù)范圍很小。

3. 狀壓DP

狀壓DP，顧名思義，就是使用狀態(tài)壓縮的動態(tài)規(guī)劃。

動態(tài)規(guī)劃問題通常有兩種，一種是對遞歸問題的記憶化求解，另一種是把大問題看作是多階段的決策求解。這里用的便是后一種，這帶來一個需求，即存儲之前的狀態(tài)，再由狀態(tài)及狀態(tài)對應(yīng)的值推演出狀態(tài)轉(zhuǎn)移方程最終得到最優(yōu)解。

二、位運算

一般基礎(chǔ)的狀壓就是將一行的狀態(tài)壓成一個數(shù)，這個數(shù)的二進制形式反映了這一行的情況。由于使用二進制數(shù)來保存被壓縮的狀態(tài)，所以要用到神奇的二進制位運算操作，將一個十進制數(shù)轉(zhuǎn)成二進制進行位運算操作再轉(zhuǎn)回十進制數(shù)。

包括：

按位與&（有0為0，其實就是且）

按位或|（有1為1，其實就是或）

按位取反~（注意負數(shù)補碼的符號，最前面的第一位是1）

異或^（相同為0，不同為1）

左移<<

右移>>