狀态壓縮DP POJ 1699解題報告

http://acm.pku.edu.cn/JudgeOnline/problem?id=1699

今天在做POJ 1699時，明顯感覺用DP可以解，但是始終找不到合适的狀态方程和子結構。在discuss中看到有人讨論用“狀态壓縮dp”求解比較友善，于是花了一下午時間去查找狀态dp的資料，在上一篇（zz）中看到了一篇講解非常詳細的介紹，于是就開始來分析POJ 1699。

看到這一題的第一直覺是全排列所有的字元串，通過回溯肯定能求出最優解，但是時間複雜度可能不能AC。于是試着尋找最優子結構，試着用dp來解。

假設min是最優解，最直接考慮的是min=min{ 第i個串排在最後時得到字串長度}。

假設dp[si][i]表示狀态si下以i字元串結尾最優值（best sequence），其中si是二進制位表示的集合，二進制位串的長度(len(si))根據字元串的個數來n确定。若si[k]=0表示目前狀态集合不包含字元串k，即第k個字元串還未放置，用k!=si表示。

例如，n=4,si=00000~01111。

則min = min {dp[2^n-1][i]}，

                       n表示字元串的個數，0<i<n。

                       2^n-1表示所有的字元串都已經放置,

                       dp[2^n-1][i]表示在所有的字元串都已經放置好的情況下，以第i個字元串結尾是的字元串長度。

則有：dp[si][i] = min {dp[sj][j] + m(i,j)}，

                  sj = si&(~(1<<i))，表示對目前狀态集出去i，得到一個規模更小的子問題sj。

                  對每一個j屬于sj，求出子問題dp[sj][j]。

這裡存在很多重複的子問題，比如當si=01101，i=0時，這時sj = 01100，這時對j=2,j=3都屬于集合sj，因為sj[2]和sj[3]都為1。

于是求解dp[s0][0]需要求解dp[s2][2]和dp[s3][3]。

而當si=01110，i=1時，這時sj=01100，于是求dp[s1][1]同樣需要求dp[s2][2]和dp[s3][3]。

考慮到上述遞歸形式和重複子問題，于是考慮用記憶化dp（記憶化遞歸搜尋）來求解問題。