動態規劃
動態規劃(dynamic programming)是運籌學的一個分支，是求解決策過程(decision process)最優化的數學方法。20世紀50年代初美國數學家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優化問題時，提出了著名的最優化原理(principle of optimality)，把多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解，創立了解決這類過程優化問題的新方法——動態規劃。
https://blog.csdn.net/hebtu666/article/category/8018091基礎總結
?
狀態壓縮
我們在進行動態規劃時，有時狀態相當復雜，看上去需要很多空間，比如一個數組才能表示一個狀態，那么就需要對狀態進行某種編碼，進行壓縮表示。
比如：狀態和某個集合有關，集合里可以有一些元素，沒有另一些元素，那么就可以用一個整數表示該集合，每個元素對應于一個bit，有該元素，則該bit就是1。
這個皇后問題就可以幫助理解https://blog.csdn.net/hebtu666/article/details/84631083
?
旅行商問題
?
旅行商問題(TravelingSalesmanProblem，TSP)是一個經典的組合優化問題。經典的TSP可以描述為：一個商品推銷員要去若干個城市推銷商品，該推銷員從一個城市出發，需要經過所有城市后，回到出發地。應如何選擇行進路線，以使總的行程最短。從圖論的角度來看，該問題實質是在一個帶權完全無向圖中，找一個權值最小的Hamilton回路。由于該問題的可行解是所有頂點的全排列，隨著頂點數的增加，會產生組合爆炸，它是一個NP完全問題。由于其在交通運輸、電路板線路設計以及物流配送等領域內有著廣泛的應用，國內外學者對其進行了大量的研究。早期的研究者使用精確算法求解該問題，常用的方法包括：分枝定界法、線性規劃法、動態規劃法等。但是，隨著問題規模的增大，精確算法將變得無能為力，因此，在后來的研究中，國內外學者重點使用近似算法或啟發式算法，主要有遺傳算法、模擬退火法、蟻群算法、禁忌搜索算法、貪婪算法和神經網絡等。
?
如圖，我們如何從0點出發，以最小代價走過所有的點？
?
分析
?
拋開這個圖，我們試想：我們可能從0點一次性走到哪些點呢？
只可能1點、2點、3點、4點（廢話）
那我們如果知道了
1）從1點開始走，經過所有的點，最后走到了0點的最小距離；a
2）從2點開始走，經過所有的點，最后走到了0點的最小距離；b
3）從3點開始走，經過所有的點，最后走到了0點的最小距離；c
4）從4點開始走，經過所有的點，最后走到了0點的最小距離；d
請再次注意：
我們可能從0點一次性走到哪些點呢？
只可能1點、2點、3點、4點（廢話）
所以我們可以從0點走到1點，再從1點經過最小距離走到0點。
2點、3點、4點同理。
那么我們取min(a+3,b+MAX,c+4,d+MAX)即可。
3為0點走到1點的距離，4為0點走到3點的距離。
MAX代表此路不通。。
?
那我們繼續思考，abcd怎么求呢？其實同樣的：
?
比如：求a
從1點開始走，經過所有的點，最后走到了0點的最小距離；a
同樣的思考：我們可能從1點一次性走到哪些點呢？
答：可以走到0點、2點、3點、4點。
注意：由于問題要求為：只能經過每一個頂點一次，所以我們要去掉0點，因為我們經過0點，最后再到0點就會重復，所以，
“經過所有的點”是不準確的，是除0點的所有的點。
所以只有三個點可能從1點走過去，我們需要求：
1）從2點開始走，經過除0點所有的點，最后走到了0點的最小距離x
2）從3點開始走，經過除0點所有的點，最后走到了0點的最小距離y
3）從4點開始走，經過除0點所有的點，最后走到了0點的最小距離z
然后取min(x+到2點的距離，y+到3點的距離，z+到4點的距離)
?
歸納表達式
1）我們會發現，每一次狀態轉移其實對應的是一個點的集合：
以后還會有經過除1，2點，經過除1，2，3點等等。
?
2）還有從哪個點開始走：
這兩個條件就可以描述當前的狀態。
我們把上面的總結用公式表示出來：
S為已經訪問過的點的集合
v表示當前所在點。
那么dp[S][v]就表示為從點v出發訪問剩余點，最終返回0點的最小長度。
我們把剛才的求解過程用公式表達出來。
?這個符號我實在沒找到，理解意思。
?
壓縮
像這樣，狀態可以根據集合表示的DP，我們稱作狀態壓縮DP。
狀態和某個集合有關，集合里可以有一些元素，沒有另一些元素，那么就可以用一個整數表示該集合，每個元素對應于一個bit，有該元素，則該bit就是1。?
本題來說，所有點都在集合里就是11111
哪個點沒在，對應的位就為0
?
注意：對于狀態不是整數而是集合的情況，通常不太容易確定DP的順序，如果確實不好想順序，可以通過記憶化搜索來做。
集合S，如果對于任意S(i)<S(j)，那么一定有i<j。所以確定了順序。
?
確定dp表的大小，有n個城市，從0開始編號，那么dp表的行數就是n，列數就是2^(n-1)
int n;
int d[MAX_N][MAX_N];//鄰接矩陣
int dp[1<<MAX_N][MAX_N];對于數字x，要看它的第i位是不是1，那么可以通過 (x >>i) & 1取出那一位來看
先用足夠大的值初始化dp數組，不要影響結果，然后核心代碼：
for(int S = (1<<n)-2 ; S >= 0 ; s--)//每一個集合
{for(int v = 0 ; v < n ; v++)//每一個出發點{for(int u = 0 ; u < n ; u++)//訪問每一個點{if(!(S>>u&1))//判斷是否在集合中{dp[S][v] = min(dp[S][v] , dp[S | 1<<u][u]+d[v][u]);}}}
}?
總結
?
當我們把狀態壓縮應用到動態規劃中，可以用來精簡狀態，節約空間，也方便轉移。
最常見的就是用二進制來表是狀態，利用各種位移運算，就可以實現O(1)的轉移。
?
