狀態轉換器，轉 狀態壓縮DP

引入?
首先來說說“狀態壓縮動態規劃”這個名稱，顧名思義，狀態壓縮動態規劃這個算法包括兩個特點，第一是“狀態壓縮”，第二是“動態規劃”。?

狀態壓縮：?

從狀態壓縮的特點來看，這個算法適用的題目符合以下的條件：?
1.解法需要保存一定的狀態數據（表示一種狀態的一個數據值），每個狀態數據通常情況下是可以通過2進制來表示的。這就要求狀態數據的每個單元只有兩種狀態，比如說棋盤上的格子，放棋子或者不放，或者是硬幣的正反兩面。這樣用0或者1來表示狀態數據的每個單元，而整個狀態數據就是一個一串0和1組成的二進制數。?
2.解法需要將狀態數據實現為一個基本數據類型，比如int，long等等，即所謂的狀態壓縮。狀態壓縮的目的一方面是縮小了數據存儲的空間，另一方面是在狀態對比和狀態整體處理時能夠提高效率。這樣就要求狀態數據中的單元個數不能太大，比如用int來表示一個狀態的時候，狀態的單元個數不能超過32（32位的機器）。?

這里舉一個可以狀態壓縮的例子，比如poj上的第1753題Flip Game（見poj1753解題報告），雖然這道題目不是用動態規劃做，但是可以用狀態壓縮，4×4的格子，每個格子的狀態為黑或者白，這樣就可以用一個16位的二進制數來表示，在實現的時候可以用一個int類型來表示這個二進制數。在狀態和狀態對比和轉換的時候可以用位操作來完成。?

位操作實現技巧：?
如果要獲得第i位的數據，判斷((data&(0X<<i))==0),若真，為0，假，為1；?
如果要設置第i位為1，data=(data|(0X1<<i));?
如果要設置第i位為0，data=(data&(~(0X1<<i)));?
如果要將第i位取反，data=(data^(0X1<<i);?
如果要取出一個數的最后一個1(lowbit)：(data&(-data))?

動態規劃：?
如果說狀態壓縮是數據結構的話，那么動態規劃應該是算法了。題目通過動態規劃來解通常有兩個動機，第一是利用遞歸的重疊子問題，進行記憶話求解，即遞歸法的優化。第二是把問題看作多階段決策的過程來求解問題。在狀態壓縮動態規劃中我們討論的是第二種動機。?

多階段決策過程求解問題的動態規劃最重要的是劃分階段和找到狀態轉移方程。對于劃分階段，是根據不同階段之間的獨立性來劃分，通常會用狀態數組的第一個下標來記錄這個階段的標記（比如01背包問題中的狀態數組第一個下標為物品的個數，棋盤放棋子問題中的狀態數組的第一個下標為棋盤的行數等等）。另一個重要的便是狀態轉移方程，狀態轉移方程是遞推時得到一個狀態數據的重要根據。通常情況下狀態數組的除了第一個下標以外都是表示狀態數據的，而狀態數組的值是和所求結果緊密結合的。在后面的幾個例題中會重點說明狀態轉移方程。?

當狀態壓縮和動態規劃結合的時候便形成了一類問題的一種算法，即狀態壓縮動態規劃的算法。這種算法最常見在棋盤問題上或者網格問題上，因為這一類問題的狀態數據的單元較少，可以通過狀態壓縮來對當前棋盤或者網格的狀態進行處理。?

例題解析?
例：在n*n(n≤20)的方格棋盤上放置n 個車，某些格子不能放，求使它們不能互相攻擊的方案總數。?
分析：?
首先看到這道題目，我們可能會想到8皇后問題，用深度優先搜索。但是這里放這道題目是用來說明此題可以狀態壓縮動態規劃，而且狀態壓縮動態規劃相比于深度優先搜索可以應對更多的變化情況和擁有更高的效率。?

用狀態壓縮動態規劃算法?
1.劃分階段，本題比較簡單，以行來劃分階段，即一行一行的放車。?
2.找狀態轉移方程，因為前i行的狀態是根據前i-1行的狀態來確定的，所以，在狀態數組中要記錄多行狀態。故設計狀態數組為f[i][x]，i表示這是前i行的狀態，x在這里是就是一個壓縮的狀態，記錄一個二進制數從而來表示前i行的狀態，f的值記錄形成前i行的x狀態有多少種方案。狀態轉移方程是f[i][a]=SUM{f[i-1][b]},下面討論a狀態與b狀態的關系。先舉個例子，如果a狀態為01011，表明前i行中的第0，1，3列都放置了一個車（從右往左看）。于是b的狀態就可能是01010，01001，00011三種狀態，于是f[3][01011]=f[2][01010]+f[2][01001]+f[2][00011]。再看普遍的情況，a-b的值的二進制表示中只有一個1。而且要保證a狀態，b狀態不能和非可用的格子沖突。綜上，狀態轉移方程為：?
f[i][a]=SUM{f[i-1][b]} (a-b的值的二進制表示中只有一個1; a,b不與題目中的約束條件沖突)?
這樣通過遞推可以得到f[n][1…1]的方案數即為最后的方案總數。?


算法總結：?
1.斷定這道題目可以用數據壓縮動態規劃來做。重點是看它的特點，是否符合狀態壓縮動態規劃的條件。?
2.劃分階段。像棋盤和網格問題大多數是一行一行的進行操作，故以行來劃分階段，當然也有其他的階段劃分方法，具體問題具體分析。?
3.找狀態轉移方程?
3.1設計狀態數組。通常數組的第一個參數為階段的標志，其他幾個參數為記錄狀態用（如果第i行的狀態可以通過第i-1行的狀態來確定，則需要一個參數，即第i行的狀態；如果像炮兵陣地那題一樣，第i行的狀態需要根據第i-1行和第i-2行來確定，則需要兩個參數，分別為第i行的狀態和第i-1行的狀態，具體見附錄）。數組的值與結果掛鉤，通常有以下幾種情況：a.題目要求一共有多少的方案，這時數組的值為當前狀態的方案數。（比如poj2411以及例題）b.題目要求最佳方案，這是數組的值為最佳方案的值。（比如poj1185炮兵陣地）。?
3.2列出狀態轉移方程，對應與上面的a，b兩種情況，a情況時，狀態轉移方程為f[i][a]=sum{f[i-1][b]}; b情況時，狀態轉移方程為f[i][a]=max{f[i][b]}+sth.?
3.3找出狀態轉移方程中a，b之間的關系。即為狀態轉移方程添加約束條件。?
4.在很多情況下需要對每一個階段的可能值進行dfs來找出所有的可能值存儲起來，以便在對每一個階段處理的時候能夠很快的運用以提高效率。