動態(tài)規(guī)劃的優(yōu)化技巧

1、動態(tài)規(guī)劃的優(yōu)化技巧沈許川 00848313 冗余冗余 求解無用的子問題求解無用的子問題 對結(jié)果無意義的引用對結(jié)果無意義的引用 狀態(tài)總數(shù)狀態(tài)總數(shù) 每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù) 每次狀態(tài)轉(zhuǎn)移的時間每次狀態(tài)轉(zhuǎn)移的時間 相互聯(lián)系相互聯(lián)系 相互制約相互制約時間復(fù)雜度一、狀態(tài)總數(shù) 狀態(tài)的選擇狀態(tài)的選擇 階段劃分階段劃分合理性完備性操作性 題目信息約束題目信息約束顯式 隱式Raucous Rockers 演唱組（USACO96）問題描述現(xiàn)有n首由Raucous Rockers 演唱組錄制的珍貴的歌曲，計劃從中選擇一些歌曲來發(fā)行m張唱片，每張唱片至多包含t分鐘的音樂，唱片中的歌曲不能重疊。按下面的

2、標(biāo)準(zhǔn)進行選擇：（1）.這組唱片中的歌曲必須按照它們創(chuàng)作的順序排序；（2）.包含歌曲的總數(shù)盡可能多。輸入n，m，t，和n首歌曲的長度，它們按照創(chuàng)作順序排序，沒有一首歌超出一張唱片的長度，而且不可能將所有歌曲的放在唱片中。輸出所能包含的最多的歌曲數(shù)目。（1n, m, t20） 方法一long1.n n首歌曲按照寫作順序排序后的長度gi, j, k前 i 首歌曲用 j 張唱片另加 k 分鐘最多可以錄制的歌曲數(shù)目 gn, m, 0 問題的最優(yōu)解轉(zhuǎn)移方程klongi，i1 gi, j, k=maxgi-1,j,k-longi，gi-1,j,kk longi，i1 gi, j, k=maxgi-1,j-1

3、,t-longi，gi-1,j,k 邊界條件 0k t-b時： a=a+1; b=longi;規(guī)劃的邊界條件：gi,0=(0,0) 0in題目所求的值：ans=maxk| gn, k(m-1,t) 狀態(tài)總數(shù)為O(n) 每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)為O(1) 每次狀態(tài)轉(zhuǎn)移的時間為O(1) 所以總的時間復(fù)雜度為O(n) 值得注意的是，空間復(fù)雜度O(n*m*t) O(n) 使用滾動數(shù)組 O(n*m*t) O(n) 二、每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù) 狀態(tài)表示決定范圍 決策量的優(yōu)化挖掘題目信息決策單調(diào)性四邊形法則abcdwa,c+wb,dwa,d+wb,c 合理組織狀態(tài) 石子合并問題(NOI95)

4、問題描述 在一個操場上擺放著一排n（n20）堆石子?，F(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。 試編程求出將n堆石子合并成一堆的最小得分和最大得分以及相應(yīng)的合并方案。方法一wi第i堆石子的石子數(shù)Ci,j將第i堆石子、第j堆石子及之間的石子合并所得最小分?jǐn)?shù)njijCkCi,k,j+Ci,j=tijki1 |,1minjippw=i,jt第i堆石子到第j堆石子總石子數(shù)si,j=i或si,j=j-1 也就是說最優(yōu)合并方案只可能是： (i) (i+1 j) 或 (i j-1) (j) si,j第i堆到第j堆石子的最優(yōu)斷開位置證明：

5、si,j=p (ipj-1)不妨設(shè) ti, ptp+1,j 由于ip，設(shè)q=si,p最優(yōu)合并方案為： (iq) (q+1.p) (p+1j) C1=Ci, q+Cq+1,p+Cp+1,j+ti, j+ti, p另取構(gòu)造方案： (iq) (q+1.p) (p+1j) C2=Ci, q+Cq+1,p+Cp+1,j+ti, j+tq+1,j 由于qp，所以ti, ptp+1,jtq+1,j 所以C1C2，這與si, j=p矛盾 狀態(tài)轉(zhuǎn)移方程優(yōu)化為： Ci,j=maxCi+1,j, Ci,j-1+ti,j ij 規(guī)劃的邊界條件是： Ci,i=0 算法的時間復(fù)雜度O(n)。方法二方法三 平行四邊形法則+

6、單調(diào)性abcdCa, c+ Cb, d Ca, d+ Cb, c證明：設(shè)k1=sa,d , k2=sb,c ，這里不妨設(shè)k1 k2 則有Ca, c+ Cb, d Ca, k1-1+ Ck1, c+ Cb, k2-1+ Ck2, d+ ta, c+ tb, d= Ca, k1-1+ Ck2, d+ Cb, k2-1+ Ck1, c+ ta, d+ tb, c Ca, k1-1+ Ck1, d+ Cb, k2-1+ Ck2, c+ ta, d+ tb, c= Ca, d+ Cb, cSi,j-1 Si,j Si+1,j證明：設(shè)Cki,j= ti, j+Ci, k-1+Ck, j 令k=si,j-1

7、，并取i k k。由于k k j-1 j，故有：Ck, j-1+ Ck, j Ck, j+ Ck, j-1在等式兩側(cè)同時加上ti, j-1+ ti, j+Ci, k-1+ Ci, k-1得：Cki, j-1+ Cki, j Cki, j+ Cki, j-1由k的定義可知Cki, j-1 Cki, j-1，故Cki, j Cki, j所以k si,j，故Si,j Si,j-1同理，可得 Si,j Si+1,j由Si,j-1 Si,j Si+1,j，可知式中，如果我們先計算了Ci-1,j,Si-1,j與Ci,j+1,Si,j+1再計算Ci,j時，k僅需考慮 Si-1,j Si,j+1中的取值。因此

8、，k的選擇，由最初的ij-1，變?yōu)榱薙i-1,j Si,j+1當(dāng)我們按照 j i 的值劃分階段時，第d階段，即計算S1,1+d,S2,2+dSi,i+dSn-d,n需時O(Sn-d+1,n-S1,d+n-d) O(n) n個階段總耗時O(n),1minjCkCi,k,j+Ci,j=tijki 從減少能夠轉(zhuǎn)移到當(dāng)前狀態(tài)的狀態(tài)數(shù)入手 大多利用題目的單調(diào)性或其他更強的特性 四邊形法則+單調(diào)性 效果很好應(yīng)用廣泛要求數(shù)學(xué)能力強（ b汗）三、每次狀態(tài)轉(zhuǎn)移的時間 減少決策時間恰當(dāng)?shù)捻樞蚯‘?dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)hash表O(1)隊列優(yōu)化O(n) n次掃描均攤為O(1)排序+二分查找 線段樹 O(n)O(logN) 減少

9、計算遞推式的時間進行預(yù)處理利用計算結(jié)果 LOSTCITY (NOI2000) 問題描述 現(xiàn)給出一張單詞表、特定的語法規(guī)則和一篇文章： 文章和單詞表中只含26個小寫英文字母az。 單詞表中的單詞只有名詞，動詞和輔詞這三種詞性，且相同詞性的單詞互不相同。單詞的長度均不超過S。單詞總數(shù)不超過N。 語法規(guī)則可簡述為：名詞短語：任意個輔詞前綴接上一個名詞；動詞短語：任意個輔詞前綴接上一個動詞；句子：以名詞短語開頭，名詞短語與動詞短語相間連接而成。 文章的長度不超過M。且已知文章是由有限個句子組成的，句子只包含有限個單詞。 編程將這篇文章劃分成最少的句子，在此前提之下，要求劃分出的單詞數(shù)最少。 L1.M

10、給出的文章 Fv(i)表示L前i個字符劃分為以動詞結(jié)尾（當(dāng)iM時，可帶任意個輔詞后綴）的最優(yōu)分解方案下劃分的句子數(shù)與單詞數(shù) Fn(i)表示L前i個字符劃分為以名詞結(jié)尾（當(dāng)iM時，可帶任意個輔詞后綴）的最優(yōu)分解方案下劃分的句子數(shù)與單詞數(shù)狀態(tài)轉(zhuǎn)移方程為：Fv(i)=minFn(j)+(0,1)，L(j+1.i)為動詞； Fv(j)+(0,1)，L(j+1.i)為輔詞，iM Fn(i)=min Fn(j)+(1,1), L(j+1.i)為名詞； Fv(j)+(0,1), L(j+1.i)為名詞； Fn(j)+(0,1), L(j+1.i)為輔詞，iM 邊界條件：Fv(0)=(1,0)； Fn(0)=

11、(, )；問題的解為：min Fv(M), Fn(M) ； 狀態(tài)總數(shù)為O(M) 每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)最多為S 在進行狀態(tài)轉(zhuǎn)移時，需要查找Lj+1.i的詞性，根據(jù)其詞性做出相應(yīng)的決策，并引用相應(yīng)的狀態(tài)。 設(shè)N100000 M1000 S20 下面就通過不同的方法查找Lj+1.i的詞性，比較它們的時間復(fù)雜度。 方法1順序查找最壞情況下需要遍歷整個單詞表 最壞情況下的時間復(fù)雜度為O(M*S*N) 比較次數(shù)最多可達1000*20*5*100000=1010 方法2采用二分查找首先排序 O(NlogN)最壞情況下的時間復(fù)雜度為O(N+M*S)*logN)最多比較次數(shù) 1000*20*5*log10000

12、0=1.6*106 方法3哈希表查找預(yù)處理構(gòu)造哈希表O(N)每次查找只需O(1)的時間算法的時間復(fù)雜度為O(N+S*M) 常數(shù)取決于hash函數(shù)的計算時間及其優(yōu)劣一般較為巨大 方法4單詞前綴樹查找（mbhyj (o)/）建立前綴樹需要O(N)的時間由于每個狀態(tài)在進行狀態(tài)轉(zhuǎn)移時需要查找的所有單詞都是分布在同一條從樹根到葉子的路徑上的，因此，如果選取從樹根走一條路徑到葉子作為基本操作，則每個狀態(tài)進行狀態(tài)轉(zhuǎn)移時的最多S次單詞查找只需O(1)的時間因此，算法總的時間復(fù)雜度為O(N+M*S) 常數(shù)很小 一般情況下比hash都要快 狀態(tài)總數(shù)狀態(tài)總數(shù) 每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù) 每次狀態(tài)轉(zhuǎn)移的

13、時間每次狀態(tài)轉(zhuǎn)移的時間 確定狀態(tài)表示確定狀態(tài)表示 之后轉(zhuǎn)移的優(yōu)化之后轉(zhuǎn)移的優(yōu)化 相互聯(lián)系相互聯(lián)系 相互制約相互制約Homework 最長上升子序列 POJ2757能處理N100000的數(shù)據(jù)，時限1000ms 有興趣的同學(xué)可以嘗試以下題目（選做）POJ1769POJ3133（請上acm, grids無描述）鷹蛋Ural 1223 一個經(jīng)典的DP優(yōu)化例題，摘自朱晨光2006年的集訓(xùn)隊論文，從各個方面對算法進行了優(yōu)化。感興趣的同學(xué)可以自己試試。 鷹蛋Ural 1223 有一堆共M個鷹蛋，一位教授想研究這些鷹蛋的堅硬度E。他是通過不斷從一幢N層的樓上向下扔鷹蛋來確定E的。當(dāng)鷹蛋從第E層樓及以下樓層落下

14、時是不會碎的，但從第（E+1）層樓及以上樓層向下落時會摔碎。如果鷹蛋未摔碎，還可以繼續(xù)使用；但如果鷹蛋全碎了卻仍未確定E，這顯然是一個失敗的實驗。教授希望實驗是成功的。 例如：若鷹蛋從第1層樓落下即摔碎，E=0；若鷹蛋從第N層樓落下仍未碎，E=N。 這里假設(shè)所有的鷹蛋都具有相同的堅硬 度 。 給 定 鷹 蛋 個 數(shù) M 與 樓 層 數(shù) N (M,N=1000) , 求最壞情況下確定E所需要的最少次數(shù)。樣例： M=1，N=10 ANS=10 （解釋：只能將這個鷹蛋從下往上依次摔）狀態(tài)定義：f(i,j): 用i個蛋在j層樓上最壞情況下確定E所需要的最少次數(shù)。 狀態(tài)轉(zhuǎn)移：i個鷹蛋 (j-w)層(i-

15、1)個鷹蛋 (w-1)層i個鷹蛋 j層f(i-1,w-1)次f(i,j-w)次算法一狀態(tài)定義：f(i,j): 用i個蛋在j層樓上最壞情況下確定E所需要的最少次數(shù)。 狀態(tài)轉(zhuǎn)移：f(i,j)=minmaxf(i-1,w-1),f(i,j-w)+1|1=w= 時，直接輸出 即可.) 1(log2n) 1(log2n算法的時間復(fù)雜度立即降為O(N2log2N) 減少了總狀態(tài)數(shù)總狀態(tài)數(shù) NlogN鷹蛋的個數(shù)沒有限制，ans=) 1(log2n 觀察可發(fā)現(xiàn)，f(i,j)具有單調(diào)性f(i,j)=f(i,j-1) (j=1)（證明部分略去，本頁備注中有） 若f(i-1,w-1)f(i,j-w),則對于w=f(

16、i,j-w),則對于ww,決策為w必?zé)o決策為w好算法三 因此，在狀態(tài)轉(zhuǎn)移中，可以像二分查找那樣，每次將w 的取值范圍縮小一半，這樣就能在 次之內(nèi)找到最佳的決策wbest。 轉(zhuǎn)移復(fù)雜度O(logN) 總復(fù)雜度O(N(log2N)2) 減少了每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)) 1(log2n算法三算法四根據(jù)這個不等式，我們可以得到如下推理：若存在一個決策w使得f(i,j)=f(i,j-1)，則f(i,j)=f(i,j-1)若所有決策w均不能使f(i,j)=f(i,j-1)，則f(i,j)=f(i,j-1)+1通過進一步挖掘狀態(tài)轉(zhuǎn)移方程，我們得到如下不等式： f(i,j-1)=f(i,j)=

17、1)算法四這里，我們設(shè)一指針p，并使p時刻滿足：f(i,p)=f(i,j-1)-1 且 f(i,p+1)=f(i,j-1)由狀態(tài)轉(zhuǎn)移方程可知，決策時f(i,p)所對應(yīng)的函數(shù)值是f(i-1,j-p-1).只需通過判斷f(i,p)與f(i-1,j-p-1)的大小關(guān)系便可以決定f(i,j)的取值。（證明見備注）算法四 因此，我們只需根據(jù)f(i,p)與f(i-1,j-p-1)的大小關(guān)系便可直接確定f(i,j)的取值，從而使每次狀態(tài)轉(zhuǎn)移的時間每次狀態(tài)轉(zhuǎn)移的時間成功地降為O(1),算法的時間復(fù)雜度降為O(Nlog2N) 當(dāng)f(i,p)=f(i-1,j-p-1)時，可以直接得出f(i,j)=f(i,j-1); 當(dāng)f(i,p)=1) 很顯然，無論有多少鷹蛋，若只試1次就只能確定一層樓，即g(1,j)=1 (j=1)g(i,j)=g(i-1,j-1)+g(i-1,j)+1 (i,j1) 我們的目標(biāo)便是找到一個x，使x滿足g(x-1,M)=N ，答案即為x. 經(jīng)過觀察，我們很快會發(fā)現(xiàn)，函數(shù)g(i,j)與組合函數(shù)C(i,j)有著驚人的相似，而且可以很容易證明對于任