【概述】

通常將以一個集合內的元素信息作為狀態(tài)且狀態(tài)總數(shù)為指數(shù)級別的動態(tài)規(guī)劃稱為狀態(tài)壓縮動態(tài)規(guī)劃。

其是一類以集合信息為狀態(tài)的特殊的動態(tài)規(guī)劃問題，主要有傳統(tǒng)集合動態(tài)規(guī)劃與基于連通性狀態(tài)壓縮的動態(tài)規(guī)劃兩種。

其原理是通過二進制位運算將狀態(tài)壓縮（用整數(shù)表示集合）作為動態(tài)規(guī)劃的狀態(tài)來解決問題。

通常具備以下兩個特點：

數(shù)據規(guī)模的某一維或幾維特別小

需要具備動態(tài)規(guī)劃問題的兩個基本性質：最優(yōu)性原理、無后效性原則

為更好的理解狀壓 DP，首先要有相關的位運算知識，關于位運算：點擊這里。

【使用條件】

在任意時刻，已經求出最優(yōu)解的狀態(tài)與尚未求出最優(yōu)解的狀態(tài)在各維度上的分界點組成了 DP 擴展的輪廓，對于某些問題，需要在動態(tài)規(guī)劃的狀態(tài)中記錄一個集合，保存這個輪廓的詳細信息，以便進行狀態(tài)轉移。

若集合大小不超過 n，集合中每個元素都是小于 k 的自然數(shù)，則可以把這個集合看作一個 n 位 k 進制數(shù)，以一個??之間的十進制整數(shù)的形式作為 DP 狀態(tài)的一維。

【使用技巧】

1.狀壓 DP 題型

1）數(shù)據 n≤16 ，但狀態(tài)總數(shù)可達指數(shù)級

2）滿足無后效性原則，通過前面的狀態(tài)知道后面的怎么選，用 1、0 來記錄狀態(tài)是否存在

2.一般定義二維數(shù)組

第一維是第幾排（如：鋪磚塊等）

第二維標識狀態(tài)，0 或 1

3.數(shù)組初始化

根據題設設置初值，一般為 memset(dp,127,sizeof(dp));

再進行狀態(tài)更新：

for(int i=0;i<n;i++) ? dp[i][1<<i]=0;?

表示 i 在 state 中存在，這里的 1<<i 就是一種只選 i 的 state

4.枚舉狀態(tài)循環(huán)求值

for(int i=1;i<=n;i++) {for(int j=0;j<(1<<m);j++){if(check(i,j))//判斷當前行滿足條件的state{for(int k=0;k<(1<<m);k++)//枚舉上一行的pre_state進行更新{...}}} }

5.判斷狀態(tài)中的每一個是否符合要求

for(int i=sum;i!=0;i=(i-1)&sum) {... }

【例題】

1.入門題

Corn Fields（POJ-3254）：點擊這里

最小總代價（洛谷-U17433）：點擊這里

Necklace（HDU-3091）：點擊這里

Most Powerful（ZOJ-3471）：點擊這里

2.TSP 問題

Hie with the Pie（POJ-3311）(狀壓+Floyd求最短路)：點擊這里

Traveling（HDU-3011）(三進制的壓縮)：點擊這里

Tourism Planning（HDU-4096）(注意滿意度的計算)：點擊這里

3.其他

炮兵陣地（POJ-1185）(三層狀態(tài)的判斷)：點擊這里

Pieces（HDU-4628）(回文字串的判斷)：點擊這里

Mondriaan's Dream（POJ-2411）(貼磚塊問題)：點擊這里

Doing Homework（HDU-1074）(狀壓+遞歸輸出)：點擊這里

方格取數(shù)(1)（HDU-1565）(需進行預處理，計算合法數(shù)據個數(shù))：點擊這里

Riddle（2018 CCPC (秦皇島站) I 題）(互斥的狀態(tài))：點擊這里

總結

以上是生活随笔為你收集整理的动态规划 —— 状压 DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。