今天是算法與數據結構專題的第16篇 ，也是動態規劃系列的第5篇。
今天文章的內容是動態規劃當中非常常見的一個分支——狀態壓縮動態規劃，很多人對於狀態壓縮畏懼如虎，但其實並沒有那麼難，希望我今天的文章能帶你們學到這個經典的應用。
二進制表示狀態
在講解多重揹包問題的時候，我們曾經講過二進制表示法來解決多重揹包。利用二進制的性質，將多個物品拆分成少數個物品，轉化成了簡單的零一揹包來解決。今天的狀態壓縮同樣離不開二進制，不過我個人感覺今天的二進制應用更加容易理解一些。
二進制的很多應用離不開集合這個概念，我們都知道在計算機當中，所有數據都是以二進制的形式存儲的。一般一個int整形是4個字節，也就是32位bit，我們通過這32位bit上0和1的組合可以表示多大21億個不同的數。如果我們把這32位bit看成是一個集合，那麼
每一個數都應該對應集合的一種狀態，並且每個數的狀態都是不同的。
比如上圖當中，我們列舉了5個二進制位，我們把其中兩個設置成了1，其餘的設置成了0。我們通過計算，可以得到6這個數字，那麼6也就代表了(00110)這個狀態。數字和狀態是一一對應的，因為每個整數轉化成二進制都是唯一的。
也就是說一個整數可以轉化成二進制數，它可以代表某個集合的一個狀態，這兩者一一對應。這一點非常重要，是後面一切推導的基礎。
狀態轉移
整數的二進制表示可以代表一個二元集合的狀態，既然是狀態就可以轉移。在此基礎上，我們可以得出另一個非常重要的結論——我們可以用整數的加減表示狀態之間的轉移。
我們還用剛才的例子來舉例，上面的圖當中我們列舉了5個二進制位，假設我們用這5個二進制位表示5個小球，這些小球的編號分別是0到4。這樣一來，剛才的6可以認為表示拿取了1號和2號兩個小球的狀態。
如果這個時候我們又拿取了3號小球，那麼集合的狀態會發生變化，我們用一張圖來表示：
上圖當中粉絲的筆表示決策，比如我們拿取了3號球就是一個決策，在這個決策的影響下，集合的狀態發生了轉移。轉移之後的集合代表的數是14，它是由之前的集合6加上轉移帶來的變化，也就是2^3得到的。
2^3剛好就代表拿取3號球這個決策，這樣我們就把整個過程串起來了。
總結一下，我們用二進制的0和1表示一個二元集合的狀態。可以簡單認為某個物品存在或者不存在的狀態。由於二進制的0和1可以轉化成一個int整數，也就是說我們用整數代表了一個集合的狀態。這樣一來，我們可以用整數的加減計算來代表集合狀態的變化。
這也就是狀態壓縮的精髓，所謂的壓縮，其實就是將一個集合壓縮成了一個整數的意思，因為整數可以作為數組的下標，這樣操作會方便我們的編碼。
旅行商問題
明白了狀態壓縮的含義之後，我們來看一道經典的例題，也就是大名鼎鼎的旅行商問題。
旅行商問題的背景很有意思，說是有一個商人想要旅行各地並進行貿易。各地之間有若干條單向的通道相連，商人從一個地方出發，想要用最短的路程把所有地區環遊一遍，請問環遊需要的最短路程是多少？在這題當中，我們假設商人從0位置出發，最後依然回到位置0。
我們來看下面這張圖來直觀地感受一下：
假設我們的商人從0位置出發，想要環遊一週之後再次回到0，那麼它所需要經歷的最短距離是多少呢？
這個圖還是比較簡單的，如果在極端情況下也就是所有點之間都有連線的時候，對於每一個點來說，它可以選擇的下一個位置一共有n-1種。那麼一共可以選擇的路線總共有n!種，這是一個非常大的值，顯然是我們不能接受的。這也是為什麼我們說旅行商問題是一個NP-Hard問題。
NP問題
既然說到了NP問題，簡單和大家聊聊NP問題的定義。
很多算法的初學者對於這些概念非常迷糊，也的確，這些概念聽起來都差不多，的確很容易搞暈。我們先從最簡單的開始介紹，首先是P問題。
P問題可以認為是已經解決的問題，這個解決的定義是可以做多項式的時間複雜度內解決。所謂的多項式，也就是 O(n^k) ，這裡的k是一個常數。與多項式相反的函數有很多，比如指數函數、階乘等等。
NP問題並不是P問題的反義，這裡的N不能理解成No，就好像noSQL不是非SQL的意思一樣。NP問題指的是可以在多項式內驗證解的問題。
比如給定一個排序的序列讓我們判斷它是不是有序的，這很簡單，我們只需要遍歷一下就好了。再比如大整數的因式分解，我們來做因式分解會很難，但是讓我們判斷一個因式分解的解法是不是正確則要簡單得多，我們直接把它們乘起來和原式比較就可以了。
顯然所有P問題都是NP問題 ，既然我們可以多項式內找到解，那麼必然我們也可以在多項式內驗證解是否正確。但是反過來是否成立呢，是否多項式時間內可以驗證解的問題，也可以通過某種算法可以在多項式時間內被解開呢？究竟是我們暫時還沒有想到算法，還是解法一開始就不存在呢？
上面的這個問題就是著名的NP=P是否成立的問題，這個問題目前仍然是一個謎，有些人相信成立，有些人不相信，這也被認為是二十一世紀的最大難題之一。
為了證明這個問題，科學家們又想出了一個辦法，就是給問題做規約。舉個例子，比如解方程，我們解一元一次方程非常簡單，而解二元一次方程則要困難一些。如果我們想出瞭解二元一次方程的辦法，那麼必然也可以用來解一元一次方程，因為我們只需要令另一個未知數等於0就是一元一次方程了。
同理，我們也可以把NP問題做轉化，將它的難度增大，
增大到極限成為一個終極問題。由於這個終極問題是所有NP問題轉化得到的，只要我們想出算法來解決了終極問題，那麼，所有的NP問題全部都迎刃而解。就比如如果我們想出瞭解N元方程的算法，那麼這一類解方程的問題就都搞定了。這種轉化之後得到的問題稱為NP完全問題，也叫做NPC問題。下面我們來看一個經典的NPC問題，即邏輯電路問題。
下圖是一個邏輯電路，假設我們知道它的輸出是True，我們也知道了電路的結構，那麼請問我們能否確定一定可以找到一個輸入的組合，使得最後的輸出是True嗎？
它顯然是一個NP問題，因為我們可以直接把解法代入電路去計算一下，就可以驗證這個解是否正確，但是想要得到答案卻很難。經過嚴謹的證明，所有NP問題都可以經過轉化得到它，也就是說如果我們找到一種解法可以在多項式內解決這個問題，那麼我們就解決了所有的NP問題。
最後，還有一個NP-Hard問題，NP-Hard問題是說所有NP問題可以經過轉化得到它，但是它本身並不是NP問題，也就是說我們無法在多項式時間內判斷它的解是否正確。
比如剛才提到的旅行商問題就是一個NP-Hard問題，因為即使我們給定了一個解，我們也
沒有辦法快速判斷給定的解是否正確，必須要遍歷完所有的情況才可以。我們驗證的複雜度就已經超出了多項式的範疇，所以它不屬於NP問題，比NP問題更加困難，所以是一個NP-Hard問題。狀態壓縮解法
說完了NP問題，我們回到算法本身。
既然我們要用動態規劃的思路來解決這個問題，就不能脫離狀態和決策。前文說了我們利用二進制可以用一個整數來表示一個集合的狀態，我們很容易會把這個狀態當成是動態規劃當中的狀態，但其實這是不對的。
單純集合之間的轉移沒有限制條件，比如之前的例子當中我們已經拿了1號球和2號球，後面只要是剩下的球都可以拿，但是旅行商問題不一樣，假設我們去過了0和1兩個地方，我們當前在位置1，我們是無法用2和5兩地之間的連線來更新這個狀態的，因為我們當前只能從1號位置出發。也就是說我們
能採取的決策是有限制的。所以我們不能只單純地拿集合的狀態來當做狀態，為了保證地點之間的移動順序正確，我們還需要加上一維，也就是當前所處的位置。所以真正的狀態是我們之前遍歷過的位置的狀態，加上當前所處的地點，這兩者的結合。
狀態確定了，決策就很簡單了，凡是當前地點能去的之前沒有去過的位置，都可以構成決策。
我們之前說過，在動態規劃問題當中，複雜度等於狀態數乘上決策數，狀態數是2^n * n，決策數就是n，所以總體的複雜度是n^2 * 2^n。雖然這個數字看起來仍然大得誇張，但是仍然要比n!小很多。
我們舉個例子來看下，如果n=10，n!=3628800，n^2*2^n = 102400，兩者相差了三十多倍。隨著n的增大，兩者的差距還會更大。
最後，我們來實現以下算法：
在acm競賽的代碼風格當中，我們通常用u表示邊的起點，v表示邊的終點。所以上面的三重循環第一種是遍歷了所有的狀態，後面兩重循環是枚舉了起點和終點，也就是所有的邊。我們遍歷的是當前這個狀態之前的最後一次移動的邊，也就是說當前的點是v，之前的點是u，所以之前的狀態是s - 2^v，決策帶來的開銷是d[u][v]，也就是從u到v的距離。
如果讀過之前文章的小夥伴，會發現這是一個逆推的動態規劃。我們枚舉當前的狀態和當前狀態的所有來源，從而找到當前狀態的最優解。如果對這個概念不熟悉的同學，可以查看一下之前動態規劃下的其他文章。
這段代碼當中有兩個細節，第一個細節是我們沒有做u的合法判斷，有可能我們u是不合法的，比如我們的集合當中只有2和3兩個點，但是我們卻枚舉了從4到5的策略。這樣是沒問題的，因為我們開始的時候把所有的狀態都設置成了無窮大，只有合法的狀態才不是無窮，由於我們希望最後得到的結果越小越好，不合法的狀態是不會被用來更新的。
第二個細節稍微隱蔽一些，就是我們在初始化的時候設置了dp[0][0] = 0。這表示我們是從空集開始的，而不是從0點開始的。因為0點已經遍歷過的狀態對應的數字是1，當然我們也可以設置成0已經訪問過了，從0點開始，這樣的話由於每個點不能重複訪問，所以最後我們是無法回到0點的，要得到正確結果我們還需要加上回到0點需要的消耗。
分析一下會發現第一點是第二點的基礎，如果我們在枚舉策略的時候都判斷一下u點是否也合法，那麼這個算法就沒有辦法執行，因為對於空集而言，所有點都是未訪問過的，也都是非法狀態，我們就找不到一個訪問過的u作為決策的起點。
如果你看不懂上面的做法也沒有關係，我再附上一種稍稍簡單一些的方法：
在這一種做法當中，我們從狀態1開始，也就是說我們把0號位置看成當前所在的點，並且已經遍歷過了，所以標記成了1。這樣的問題是我們沒有辦法再回到0了，因為一個點只能走一次，所以最後的時候需要再尋找回到0點的最優路徑。
(1 << n) - 1的值是從0到n-1個二進制位都是1的值，表示這n個位置全部已經遍歷過了。然後我們遍歷所有回到0點的出發點，找到距離最近的那條。相比於上面的做法，這種做法更容易理解一些，但是代碼多寫幾行，但是更容易理解一些。我建議如果直接理解第一段代碼有困難的話，可以先搞懂第二段，然後再想明白為什麼第一段代碼也成立。
總結
不知道有多少人成功看到了這裡，動態規劃的確不簡單，第一次學的話會覺得很困難難以理解是正常的。但是它是屬於那種入門之前覺得特別難，但是
一旦想明白了之後就特別簡單的問題。而且大家從代碼量上也看得出來，我用了幾千字描述的算法，寫出來居然只有十幾行。動態規劃算法一直都是如此，代碼不長，但每一行都是精髓。從這點上來說，它的性價比還真的是蠻高的。
好了，今天的文章就是這些，如果覺得有所收穫，請順手點個關注或者轉發吧，你們的舉手之勞對我來說很重要。
