第9章動態(tài)規(guī)劃初步

1、第9章動態(tài)規(guī)劃初步學(xué)習(xí)目標(biāo)理解狀態(tài)和狀態(tài)轉(zhuǎn)移方程理解最優(yōu)子結(jié)構(gòu)和重疊子問題熟練運用遞推法和記憶化搜索求解數(shù)字三角形問題熟悉DAG上動態(tài)規(guī)劃的常見思路、兩種狀態(tài)定義方法和刷表法掌握記憶化搜索在實現(xiàn)方面的注意事項掌握記憶化搜索和遞推中輸出方案的方法掌握遞推中滾動數(shù)組的使用方法熟練解決經(jīng)典動態(tài)規(guī)劃問題動態(tài)規(guī)劃的理論性和實踐性都比較強(qiáng)，一方面需要理解“狀態(tài)”、“狀態(tài)轉(zhuǎn)移”、“最優(yōu)子結(jié)構(gòu)”、“重疊子問題”等概念，另一方面又需要根據(jù)題目的條件靈活設(shè)計算法。可以這樣說，對動態(tài)規(guī)劃的掌握情況在很大程度上能直接影響一個選手的分析和建模能力。9.1 數(shù)字三角形動態(tài)規(guī)劃是一種用途很廣的問題求解方法，它本身并不是一個

2、特定的算法，而是一種思想，一種手段。下面通過一個題目闡述動態(tài)規(guī)劃的基本思路和特點。9.1.1 問題描述與狀態(tài)定義數(shù)字三角形問題。有一個由非負(fù)整數(shù)組成的三角形，第一行只有一個數(shù)，除了最下行之外每個數(shù)的左下方和右下方各有一個數(shù)，如圖9-1所示。（a）數(shù)字三角形 （b）格子編號圖9-1 數(shù)字三角形問題從第一行的數(shù)開始，每次可以往左下或右下走一格，直到走到最下行，把沿途經(jīng)過的數(shù)全部加起來。如何走才能使得這個和盡量大？【分析】如果熟悉回溯法，可能會立刻發(fā)現(xiàn)這是一個動態(tài)的決策問題：每次有兩種選擇左下或右下。如果用回溯法求出所有可能的路線，就可以從中選出最優(yōu)路線。但和往常一樣，回溯法的效率太低：一個n層數(shù)字

3、三角形的完整路線有2n-1條，當(dāng)n很大時回溯法的速度將讓人無法忍受。為了得到高效的算法，需要用抽象的方法思考問題：把當(dāng)前的位置(i, j)看成一個狀態(tài)（還記得嗎？），然后定義狀態(tài)(i, j)的指標(biāo)函數(shù)d(i, j)為從格子(i, j)出發(fā)時能得到的最大和（包括格子(i, j)本身的值）。在這個狀態(tài)定義下，原問題的解是d(1, 1)。下面看看不同狀態(tài)之間是如何轉(zhuǎn)移的。從格子(i, j)出發(fā)有兩種決策。如果往左走，則走到(i+1, j)后需要求“從(i+1, j)出發(fā)后能得到的最大和”這一問題，即d(i+1, j)。類似地，往右走之后需要求解d(i+1, j+1)。由于可以在這兩個決策中自由選擇，

4、所以應(yīng)選擇d(i+1,j)和d(i+1,j+1)中較大的一個。換句話說，得到了所謂的狀態(tài)轉(zhuǎn)移方程：如果往左走，那么最好情況等于(i, j)格子里的值a(i, j)與“從(i+1, j)出發(fā)的最大總和”之和，此時需注意這里的“最大”二字。如果連“從(i+1,j)出發(fā)走到底部”這部分的和都不是最大的，加上a(i, j)之后肯定也不是最大的。這個性質(zhì)稱為最優(yōu)子結(jié)構(gòu)（optimal substructure），也可以描述成“全局最優(yōu)解包含局部最優(yōu)解”。不管怎樣，狀態(tài)和狀態(tài)轉(zhuǎn)移方程一起完整地描述了具體的算法。提示9-1：動態(tài)規(guī)劃的核心是狀態(tài)和狀態(tài)轉(zhuǎn)移方程。9.1.2 記憶化搜索與遞推有了狀態(tài)轉(zhuǎn)移方程之后

5、，應(yīng)怎樣計算呢？方法1：遞歸計算。程序如下（需注意邊界處理）：int solve(int i, int j) return aij + (i = n ? 0 : max(solve(i+1,j),solve(i+1,j+1);圖9-2 重疊子問題這樣做是正確的，但時間效率太低，其原因在于重復(fù)計算。如圖9-2所示為函數(shù)solve(1, 1)對應(yīng)的調(diào)用關(guān)系樹。看到了嗎？solve(3, 2)被計算了兩次（一次是solve(2, 1)需要的，一次是solve(2, 2)需要的）。也許讀者會認(rèn)為重復(fù)算一兩個數(shù)沒有太大影響，但事實是：這樣的重復(fù)不是單個結(jié)點，而是一棵子樹。如果原來的三角形有n層，則調(diào)用關(guān)

6、系樹也會有n層，一共有2n-1個結(jié)點。提示9-2：用直接遞歸的方法計算狀態(tài)轉(zhuǎn)移方程，效率往往十分低下。其原因是相同的子問題被重復(fù)計算了多次。方法2：遞推計算。程序如下（需再次注意邊界處理）：int i, j;for(j = 1; j = 1; i-)for(j = 1; j = 0) return dij; return dij = aij + (i = n ? 0 : max(solve(i+1,j),solve(i+1,j+1);上述程序依然是遞歸的，但同時也把計算結(jié)果保存在數(shù)組d中。題目中說各個數(shù)都是非負(fù)的，因此如果已經(jīng)計算過某個dij，則它應(yīng)是非負(fù)的。這樣，只需把所有d初始化為-1，即

7、可通過判斷是否dij0得知它是否已經(jīng)被計算過。圖9-3 記憶化搜索最后，千萬不要忘記在計算之后把它保存在dij中。根據(jù)C語言“賦值語句本身有返回值”的規(guī)定，可以把保存dij的工作合并到函數(shù)的返回語句中。上述程序的方法稱為記憶化（memoization），它雖然不像遞推法那樣顯式地指明了計算順序，但仍然可以保證每個結(jié)點只訪問一次，如圖9-3所示。由于i和j都在1n之間，所有不相同的結(jié)點一共只有O(n2)個。無論以怎樣的順序訪問，時間復(fù)雜度均為O(n2)。從2nn2是一個巨大的優(yōu)化，這正是利用了數(shù)字三角形具有大量重疊子問題的特點。提示9-4：可以用記憶化搜索的方法計算狀態(tài)轉(zhuǎn)移方程。當(dāng)采用記憶化搜索

8、時，不必事先確定各狀態(tài)的計算順序，但需要記錄每個狀態(tài)“是否已經(jīng)計算過”。9.2 DAG上的動態(tài)規(guī)劃有向無環(huán)圖上的動態(tài)規(guī)劃是學(xué)習(xí)動態(tài)規(guī)劃的基礎(chǔ)。很多問題都可以轉(zhuǎn)化為DAG上的最長路、最短路或路徑計數(shù)問題。9.2.1 DAG模型嵌套矩形問題。有n個矩形，每個矩形可以用兩個整數(shù)a、b描述，表示它的長和寬。矩形X(a,b)可以嵌套在矩形Y(c, d)中，當(dāng)且僅當(dāng)ac，bd，或者bc，a 0) return ans;ans = 1;for(int j = 1; j = n; j+)if(Gij) ans = max(ans, dp(j)+1);return ans;這里用到了一個技巧：為表項di聲明一個

9、引用ans。這樣，任何對ans的讀寫實際上都是在對di進(jìn)行。當(dāng)di換成dijklmn這樣很長的名字時，該技巧的優(yōu)勢就會很明顯。提示9-5：在記憶化搜索中，可以為正在處理的表項聲明一個引用，簡化對它的讀寫操作。原題還有一個要求：如果有多個最優(yōu)解，矩形編號的字典序應(yīng)最小。還記得第6章中的例題“理想路徑”嗎？方法與其類似。將所有d值計算出來以后，選擇最大di所對應(yīng)的i。如果有多個i，則選擇最小的i，這樣才能保證字典序最小。接下來可以選擇且的任何一個j。為了讓方案的字典序最小，應(yīng)選擇其中最小的j。程序如下輸出的最后會有一個多余空格，并且沒有回車符。在使用時，應(yīng)在主程序調(diào)用print_ans后加一個回車

10、符。如果比賽明確規(guī)定行末不允許有多余空格，則可以像前面介紹的那樣加一個變量first來幫助判斷。：void print_ans(int i) printf(%d , i);for(int j = 1; j = 0) return ans;ans = 0;for(int i = 1; i= Vi) ans = max(ans, dp(S-Vi)+1);return ans;注意到區(qū)別了嗎？由于在本題中，路徑長度是可以為0的（S本身可以是0），所以不能再用d=0表示“這個d值還沒有算過”。相應(yīng)地，初始化時也不能再把d全設(shè)為0，而要設(shè)置為一個負(fù)值在正常情況下是取不到的。常見的方法是用-1來表示“沒有

11、算過”，則初始化時只需用memset(d,-1, sizeof(d)即可。至此，已完整解釋了上面的代碼為什么把if(ans0)改成了if(ans=0)。提示9-7：當(dāng)程序中需要用到特殊值時，應(yīng)確保該值在正常情況下不會被取到。這不僅意味著特殊值不能有“正常的理解方式”，而且也不能在正常運算中“意外得到”。不知讀者有沒有看出，上述代碼有一個致命的錯誤，即由于結(jié)點S不一定真的能到達(dá)結(jié)點0，所以需要用特殊的dS值表示“無法到達(dá)”，但在上述代碼中，如果S根本無法繼續(xù)往前走，返回值是0，將被誤以為是“不用走，已經(jīng)到達(dá)終點”的意思。如果把a(bǔ)ns初始化為-1呢？別忘了-1代表“還沒算過”，所以返回-1相當(dāng)于放

12、棄了自己的勞動成果。如果把a(bǔ)ns初始化為一個很大的整數(shù)，例如230呢？如果一開始就這么大，ans = max(ans, dp(i)+1)還能把a(bǔ)ns變回“正常值”嗎？如果改成很小的整數(shù)，例如-230呢？從目前來看，它也會被認(rèn)為是“還沒算過”，但至少可以和所有d的初值分開只需把代碼中if(ans=0)改為if(ans!=-1)即可，如下所示：int dp(int S)int& ans = dS;if(ans !=-1) return ans;ans = -(130);for(int i = 1; i= Vi) ans = max(ans, dp(S-Vi)+1);return ans;提示9-8

13、：在記憶化搜索中，如果用特殊值表示“還沒算過”，則必須將其和其他特殊值（如無解）區(qū)分開。上述錯誤都是很常見的，甚至“頂尖高手”有時也會一時糊涂，掉入陷阱。意識到這些問題，尋求解決方案是不難的，但就怕調(diào)試很久以后仍然沒有發(fā)現(xiàn)是哪里出了問題。另一個解決方法是不用特殊值表示“還沒算過”，而用另外一個數(shù)組visi表示狀態(tài)i是否被訪問過，如下所示：int dp(int S)if(visS) return dS;visS = 1;int& ans = dS;ans = -(130);for(int i = 1; i= Vi) ans = max(ans, dp(S-Vi)+1);return ans;盡管

14、多了一個數(shù)組，但可讀性增強(qiáng)了許多：再也不用擔(dān)心特殊值之間的沖突了，在任何情況下，記憶化搜索的初始化都可以用memset(vis, 0, sizeof(vis)如果狀態(tài)比較復(fù)雜，推薦用STL中的map而不是普通數(shù)組保存狀態(tài)值。這樣，判斷狀態(tài)S是否算過只需用if(d.count(S)即可。實現(xiàn)。提示9-9：在記憶化搜索中，可以用vis數(shù)組記錄每個狀態(tài)是否計算過，以占用一些內(nèi)存為代價增強(qiáng)程序的可讀性，同時減少出錯的可能。本題要求最小、最大兩個值，記憶化搜索就必須寫兩個。在這種情況下，用遞推更加方便（此時需注意遞推的順序）：minv0 = maxv0 = 0;for(int i = 1; i = S;

15、 i+)minvi = INF; maxvi = -INF;for(int i = 1; i = S; i+)for(int j = 1; j = Vj)minvi = min(minvi, minvi-Vj + 1);maxvi = max(maxvi, maxvi-Vj + 1); printf(%d %dn, minvS, maxvS);如何輸出字典序最小的方案呢？剛剛介紹的方法仍然適用，如下所示：void print_ans(int* d, int S)for(int i = 1; i =Vi & dS=dS-Vi+1)printf(%d , i); print_ans(d, S-Vi

16、);break; 然后分別調(diào)用 print_ans(min, S)（注意在后面要加一個回車符）和print_ans(max, S)即可。輸出路徑部分和上題的區(qū)別是，上題打印的是路徑上的點，而這里打印的是路徑上的邊。還記得數(shù)組可以作為指針傳遞嗎？這里需要強(qiáng)調(diào)的一點是：數(shù)組作為指針傳遞時，不會復(fù)制數(shù)組中的數(shù)據(jù)，因此不必?fù)?dān)心這樣會帶來不必要的時間開銷。提示9-10：當(dāng)用遞推法計算出各個狀態(tài)的指標(biāo)之后，可以用與記憶化搜索完全相同的方式打印方案。很多用戶喜歡另外一種打印路徑的方法：遞推時直接用min_coinS記錄滿足minS =minS-Vi+1的最小的i，則打印路徑時可以省去print_ans函數(shù)中

17、的循環(huán)，并可以方便地把遞歸改成迭代（原來的也可以改成迭代，但不那么自然）。具體來說，需要把遞推過程改成以下形式：for(int i = 1; i = S; i+)for(int j = 1; j = Vj)if(mini mini-Vj + 1)mini = mini-Vj + 1;min_coini = j; if(maxi ”和“=”和“”和“=”和“=”才能求出字典序最小解。在求出min_coin和max_coin之后，只需調(diào)用print_ans(min_coin, S)和print_ans(max_coin, S)即可。void print_ans(int* d, int S)whil

18、e(S)printf(%d , dS); S -= VdS; 該方法是一個“用空間換時間”的經(jīng)典例子用min_ coin和max_coin數(shù)組消除了原來print_ans中的循環(huán)。提示9-11：無論是用記憶化搜索還是遞推，如果在計算最優(yōu)值的同時“順便”算出各個狀態(tài)下的第一次最優(yōu)決策，則往往能讓打印方案的過程更加簡單、高效。這是一個典型的“用空間換時間”的例子。9.2.4 小結(jié)與應(yīng)用舉例本節(jié)介紹了動態(tài)規(guī)劃的經(jīng)典應(yīng)用：DAG中的最長路和最短路。和9.1節(jié)中的數(shù)字三角形問題一樣，DAG的最長路和最短路都可以用記憶化搜索和遞推兩種實現(xiàn)方式。打印解時既可以根據(jù)d值重新計算出每一步的最優(yōu)決策，也可以在動態(tài)

19、規(guī)劃時“順便”記錄下每步的最優(yōu)決策。由于DAG最長（短）路的特殊性，有兩種“對稱”的狀態(tài)定義方式。狀態(tài)1：設(shè)d(i)為從i出發(fā)的最長路，則。狀態(tài)2：設(shè)d(i)為以i結(jié)束的最長路，則。如果使用狀態(tài)2，“硬幣問題”就變得和“嵌套矩形問題”幾乎一樣了（唯一的區(qū)別是：“嵌套矩形問題”還需要取所有d(i)的最大值）！9.2.3節(jié)中有意介紹了比較麻煩的狀態(tài)1，主要是為了展示一些常見技巧和陷阱，實際比賽中不推薦使用。使用狀態(tài)2時，有時還會遇到一個問題：狀態(tài)轉(zhuǎn)移方程可能不好計算，因為在很多時候，可以方便地枚舉從某個結(jié)點i出發(fā)的所有邊(i,j)，卻不方便“反著”枚舉(j,i)。特別是在有些題目中，這些邊具有明顯

20、的實際背景，對應(yīng)的過程不可逆。這時需要用“刷表法”。什么是“刷表法”呢？傳統(tǒng)的遞推法可以表示成“對于每個狀態(tài)i，計算f(i)”，或者稱為“填表法”。這需要對于每個狀態(tài)i，找到f(i)依賴的所有狀態(tài)，在某些情況下并不方便。另一種方法是“對于每個狀態(tài)i，更新f(i)所影響到的狀態(tài)”，或者稱為“刷表法”。對應(yīng)到DAG最長路的問題中，就相當(dāng)于按照拓?fù)湫蛎杜ei，對于每個i，枚舉邊(i,j)，然后更新dj = max(dj, di+1)。注意，一般不把這個式子叫做“狀態(tài)轉(zhuǎn)移方程”，因為它不是一個可以直接計算dj的方程，而只是一個更新公式。提示9-12：傳統(tǒng)的遞推法可以表示成“對于每個狀態(tài)i，計算f(i)”

21、，或者稱為“填表法”。這需要對于每個狀態(tài)i，找到f(i)依賴的所有狀態(tài)，在某些時候并不方便。另一種方法是“對于每個狀態(tài)i，更新f(i)所影響到的狀態(tài)”，或者稱為“刷表法”，有時比填表法方便。但需要注意的是，只有當(dāng)每個狀態(tài)所依賴的狀態(tài)對它的影響相互獨立時才能用刷表法。例題9-1 城市里的間諜（A Spy in the Metro, ACM/ICPC World Finals 2003, UVa1025）某城市的地鐵是線性的，有n（2n50）個車站，從左到右編號為1n。有M1輛列車從第1站開始往右開，還有M2輛列車從第n站開始往左開。在時刻0，Mario從第1站出發(fā)，目的是在時刻T（0T200）會

22、見車站n的一個間諜。在車站等車時容易被抓，所以她決定盡量躲在開動的火車上，讓在車站等待的總時間盡量短。列車靠站停車時間忽略不計，且Mario身手敏捷，即使兩輛方向不同的列車在同一時間靠站，Mario也能完成換乘。輸入第1行為n，第2行為T，第3行有n-1個整數(shù)t1, t2, tn-1（1ti70），其中ti表示地鐵從車站i到i+1的行駛時間（兩個方向一樣）。第4行為M1（1M150），即從第1站出發(fā)向右開的列車數(shù)目。第5行包含M1個整數(shù)d1, d2, dM1（0di250，didi+1），即各列車的出發(fā)時間。第6、7行描述從第n站出發(fā)向左開的列車，格式同第4、5行。輸出僅包含一行，即最少等待時

23、間。無解輸出impossible。【分析】時間是單向流逝的，是一個天然的“序”。影響到?jīng)Q策的只有當(dāng)前時間和所處的車站，所以可以用d(i,j)表示時刻i，你在車站j（編號為1n），最少還需要等待多長時間。邊界條件是d(T,n)=0，其他d(T,i)（i不等于n）為正無窮。有如下3種決策。決策1：等1分鐘。決策2：搭乘往右開的車（如果有）。決策3：搭乘往左開的車（如果有）。主過程的代碼如下：for(int i = 1; i = 0; i-)for(int j = 1; j = n; j+) dpij = dpi+1j + 1; /等待一個單位if(j n & has_trainij0 & i+tj

24、 1 & has_trainij1 & i+tj-1 = T) dpij = min(dpij, dpi+tj-1j-1); /左 /輸出cout Case Number +kase = INF) cout impossiblen;else cout dp01 j。這樣，不管是哪個人，下一步只能走到i+1, i+2,這些點。可是，如果走到i+2，情況變成了“1i和i+2，但是i+1沒走過”，無法表示成狀態(tài)！怎么辦？禁止這樣的決策！也就是說，只允許其中一個人走到i+1，而不能走到i+2, i+3,。換句話說，狀態(tài)d(i,j)只能轉(zhuǎn)移到d(i+1,j)和d(i+1,i)第二個人走到i+1時本應(yīng)轉(zhuǎn)移

25、到d(i,i+1)，但是根據(jù)此處規(guī)定，必須寫成d(i+1,i)?？墒沁@樣做產(chǎn)生了一個問題：上述“霸道”的規(guī)定是否可能導(dǎo)致漏解呢？不會。因為如果第一個人直接走到了i+2，那么它再也無法走到i+1了，只能靠第二個人走到i+1。既然如此，現(xiàn)在就讓第二個人走到i+1，并不會丟失解。邊界是d(n-1,j)=dist(n-1,n)+dist(j,n)，其中dist(a,b)表示點a和b之間的距離。因為根據(jù)定義，所有點都走過了，兩個人只需直接走到終點。所求結(jié)果是dist(1,2)+d(2,1)，因為第一步一定是某個人走到了第二個點，根據(jù)定義，這就是d(2,1)。狀態(tài)總數(shù)有O(n2)個，每個狀態(tài)的決策只有兩個

26、，因此總時間復(fù)雜度為O(n2)。9.3 多階段決策問題還記得“多階段決策問題”嗎？在回溯法中曾提到過該問題。簡單地說，每做一次決策就可以得到解的一部分，當(dāng)所有決策做完之后，完整的解就“浮出水面”了。在回溯法中，每次決策對應(yīng)于給一個結(jié)點產(chǎn)生新的子樹，而解的生成過程對應(yīng)一棵解答樹，結(jié)點的層數(shù)就是“下一個待填充位置”cur。9.3.1 多段圖的最短路多段圖是一種特殊的DAG，其結(jié)點可以劃分成若干個階段，每個階段只由上一個階段所決定。下面舉一個例子：例題9-4 單向TSP（Unidirectional TSP, UVa 116）給一個m行n列（m10，n100）的整數(shù)矩陣，從第一列任何一個位置出發(fā)每次

27、往右、右上或右下走一格，最終到達(dá)最后一列。要求經(jīng)過的整數(shù)之和最小。整個矩陣是環(huán)形的，即第一行的上一行是最后一行，最后一行的下一行是第一行。輸出路徑上每列的行號。多解時輸出字典序最小的。圖9-5中是兩個矩陣和對應(yīng)的最優(yōu)路線（唯一的區(qū)別是最后一行）。圖9-5 矩陣對應(yīng)的最優(yōu)路線【分析】在這個題目中，每一列就是一個階段，每個階段都有3種決策：直行、右上和右下。提示9-13：多階段決策的最優(yōu)化問題往往可以用動態(tài)規(guī)劃解決，其中，狀態(tài)及其轉(zhuǎn)移類似于回溯法中的解答樹。解答樹中的“層數(shù)”，也就是遞歸函數(shù)中的“當(dāng)前填充位置”cur，描述的是即將完成的決策序號，在動態(tài)規(guī)劃中被稱為“階段”。有了前面的經(jīng)驗，不難設(shè)計

28、出狀態(tài)：設(shè)d(i,j)為從格子(i,j)出發(fā)到最后一列的最小開銷。但是本題不僅要輸出解，還要求字典序最小，這就需要在計算d(i,j)的同時記錄“下一列的行號”的最小值（當(dāng)然是在滿足最優(yōu)性的前提下），細(xì)節(jié)參見代碼：int ans = INF, first = 0; for(int j = n-1; j = 0; j-) /逆推for(int i = 0; i m; i+) if(j = n-1) dij = aij;/邊界else int rows3 = i, i-1, i+1; if(i = 0) rows1 = m-1;/第0行“上面”是第m-1行 if(i = m-1) rows2 = 0

29、;/第m-1行“下面”是第0行 sort(rows, rows+3);/重新排序，以便找到字典序最小的dij = INF;for(int k = 0; k 3; k+) int v = drowskj+1 + aij;if(v dij) dij = v; nextij = rowsk; if(j = 0 & dij ans) ans = dij; first = i; printf(%d, first+1);/輸出第1列for(int i = nextfirst0, j = 1; j n時d(i, j)=0，j= 1; i-)for(int j = 0; j = Vi) dij max(dij

30、,di+1j-Vi+Wi);前面說過，i必須逆序枚舉，但j的循環(huán)次序是無關(guān)緊要的。規(guī)劃方向。聰明的讀者也許看出來了，還有另外一種“對稱”的狀態(tài)定義：用f(i,j)表示“把前i個物品裝到容量為j的背包中的最大總重量”，其狀態(tài)轉(zhuǎn)移方程也不難得出：邊界是類似的：i=0時為0，j0時為負(fù)無窮，最終答案為f(n,C)。代碼也是類似的：for(int i = 1; i = n; i+)for(int j = 0; j = Vi) fij = max(fij, fi-1j-Vi+Wi); 看上去這兩種方式是完全對稱的，但其實存在細(xì)微區(qū)別：新的狀態(tài)定義f(i, j)允許邊讀入邊計算，而不必把V和W保存下來。f

31、or(int i = 1; i = n; i+)scanf(%d%d, &V, &W);for(int j = 0; j = V) fij = max(fij,fi-1j-V+W); 滾動數(shù)組。更奇妙的是，還可以把數(shù)組f變成一維的：memset(f, 0, sizeof(f);for(int i = 1; i = 0; j-)if(j = V) fj = max(fj, = fj-V+W);圖9-6 0-1背包問題的計算順序為什么這樣做是正確的呢？下面來看一下f(i, j)的計算過程，如圖9-6所示。f數(shù)組是從上到下、從右往左計算的。在計算f(i, j)之前，fj里保存的就是f(i-1, j)

32、的值，而fj-W里保存的是f(i-1, j-W)而不是f(i, j-W)別忘了j是逆序枚舉的，此時f(i, j-W)還沒有算出來。這樣，fj=(maxj, fj-V+W)實際上是把保存在fj中，覆蓋掉fj原來的f(i-1, j)。提示9-17：在遞推法中，如果計算順序很特殊，而且計算新狀態(tài)所用到的原狀態(tài)不多，可以嘗試用滾動數(shù)組減少內(nèi)存開銷。滾動數(shù)組雖好，但也存在一些不盡如人意的地方，例如，打印方案較困難。當(dāng)動態(tài)規(guī)劃結(jié)束之后，只有最后一個階段的狀態(tài)值，而沒有前面的值。不過這也不能完全歸咎于滾動數(shù)組，規(guī)劃方向也有一定責(zé)任即使用二維數(shù)組，打印方案也不是特別方便。事實上，對于“前i個物品”這樣的規(guī)劃方

33、向，只能用逆向的打印方案，而且還不能保證它的字典序最?。ㄗ值湫虮容^是從前往后的）。提示9-18：在使用滾動數(shù)組后，解的打印變得困難了，所以在需要打印方案甚至要求字典序最小方案的場合，應(yīng)慎用滾動數(shù)組。例題9-5 勁歌金曲（Jin Ge Jin Qu hao, Rujia Lius Present 6, UVa 12563）如果問一個麥霸：“你在KTV里必唱的曲目有哪些？”得到的答案通常都會包含一首“神曲”：古巨基的勁歌金曲。為什么呢？一般來說，KTV不會在“時間到”的時候魯莽地把正在唱的歌切掉，而是會等它放完。例如，在還有15秒時再唱一首2分鐘的歌，則實際上多唱了105秒。但是融合了37首歌曲的

34、勁歌金曲長達(dá)11分18秒還有勁歌金曲2和勁歌金曲3，但本題不予考慮。，如果唱這首，相當(dāng)于多唱了663秒！假定你正在唱KTV，還剩t秒時間。你決定接下來只唱你最愛的n首歌（不含勁歌金曲）中的一些，在時間結(jié)束之前再唱一個勁歌金曲，使得唱的總曲目盡量多（包含勁歌金曲），在此前提下盡量晚的離開KTV。輸入n（n50），t（t109）和每首歌的長度（保證不超過3分鐘顯然大多數(shù)歌的長度都大于3分鐘，但是KTV可以“切歌”，因此這里的“長度”實際上是指“想唱的時間長度”。），輸出唱的總曲目以及時間總長度。輸入保證所有n+1首曲子的總長度嚴(yán)格大于t?！痉治觥侩m說t109，但由于所有n+1首曲子的總長度嚴(yán)格大于

35、t，實際上t不會超過180n+678。這樣就可以轉(zhuǎn)化為0-1背包問題了。細(xì)節(jié)留給讀者思考。9.4 更多經(jīng)典模型本節(jié)介紹一些常見結(jié)構(gòu)中的動態(tài)規(guī)劃，序列、表達(dá)式、凸多邊形和樹。盡管它們的形式和解法千差萬別，但都用到了動態(tài)規(guī)劃的思想：從復(fù)雜的題目背景中抽象出狀態(tài)表示，然后設(shè)計它們之間的轉(zhuǎn)移。9.4.1 線性結(jié)構(gòu)上的動態(tài)規(guī)劃最長上升子序列問題（LIS）。給定n個整數(shù)A1, A2, An，按從左到右的順序選出盡量多的整數(shù)，組成一個上升子序列（子序列可以理解為：刪除0個或多個數(shù)，其他數(shù)的順序不變）。例如序列1, 6, 2, 3, 7, 5，可以選出上升子序列1, 2, 3, 5，也可以選出1, 6, 7，

36、但前者更長。選出的上升子序列中相鄰元素不能相等?！痉治觥吭O(shè)d(i)為以i結(jié)尾的最長上升子序列的長度，則d(i)=max0,d(j)|ji, AjAi+1，最終答案是maxd(i)。如果LIS中的相鄰元素可以相等，把小于號改成小于等于號即可。上述算法的時間復(fù)雜度為O(n2)。算法競賽入門經(jīng)典中介紹了一種方法把它優(yōu)化到O(nlogn)，有興趣的讀者可以自行閱讀。最長公共子序列問題（LCS）。給兩個子序列A和B，如圖9-7所示。求長度最大的公共子序列。例如1, 5, 2, 6, 8, 7和2, 3, 5, 6, 9, 8, 4的最長公共子序列為5, 6, 8（另一個解是2, 6, 8）。圖9-7 子

37、序列A和B【分析】設(shè)d(i,j)為A1,A2,Ai和B1,B2,Bj的LCS長度，則當(dāng)Ai=Aj時d(i,j)=d(i-1,j-1)+1，否則d(i,j)=maxd(i-1,j),d(i,j-1)，時間復(fù)雜度為O(nm)，其中n和m分別是序列A和B的長度。例題9-6 照明系統(tǒng)設(shè)計（Lighting System Design, UVa 11400）你的任務(wù)是設(shè)計一個照明系統(tǒng)。一共有n（n1000）種燈泡可供選擇，不同種類的燈泡必須用不同的電源，但同一種燈泡可以共用一個電源。每種燈泡用4個數(shù)值表示：電壓值V（V132000），電源費用K（K1000），每個燈泡的費用C（C10）和所需燈泡的數(shù)量L

38、（1L100）。假定通過所有燈泡的電流都相同，因此電壓高的燈泡功率也更大。為了省錢，可以把一些燈泡換成電壓更高的另一種燈泡以節(jié)省電源的錢（但不能換成電壓更低的燈泡）。你的任務(wù)是計算出最優(yōu)方案的費用?！痉治觥渴紫瓤梢缘玫揭粋€結(jié)論：每種電壓的燈泡要么全換，要么全不換。因為如果只換部分燈泡，如V=100有兩個燈泡，把其中一個換成V=200的，另一個不變，則V=100和V=200兩種電源都需要，不劃算（若一個都不換則只需要V=100一種電源）。先把燈泡按照電壓從小到大排序。設(shè)si為前i種燈泡的總數(shù)量（即L值之和），di為燈泡1i的最小開銷，則di = mindj + (si-sj)*ci + ki)，

39、表示前j個先用最優(yōu)方案買，然后第j+1i個都用第i號的電源。答案為dn。例題9-7 劃分成回文串（Partitioning by Palindromes, UVa 11584）輸入一個由小寫字母組成的字符串，你的任務(wù)是把它劃分成盡量少的回文串。例如，racecar本身就是回文串；fastcar只能分成7個單字母的回文串，aaadbccb最少分成3個回文串：aaa, d, bccb。字符串長度不超過1000。【分析】di為字符0i劃分成的最小回文串的個數(shù)，則di = mindj + 1 | sj+1i是回文串。注意頻繁的要判斷回文串。狀態(tài)O(n)個，決策O(n)個，如果每次轉(zhuǎn)移都需要O(n)時間

40、判斷，總時間復(fù)雜度會達(dá)到O(n3)?？梢韵扔肙(n2)時間預(yù)處理si.j是否為回文串。方法是枚舉中心，然后不斷向左右延伸并且標(biāo)記當(dāng)前子串是回文串，直到延伸的左右字符不同為止。這樣一來，每次轉(zhuǎn)移的時間降為了O(1)，總時間復(fù)雜度為O(n2)。例題9-8 顏色的長度（Color Length, ACM/ICPC Daejeon 2011, UVa1625）輸入兩個長度分別為n和m（n,m5000）的顏色序列，要求按順序合并成同一個序列，即每次可以把一個序列開頭的顏色放到新序列的尾部。例如，兩個顏色序列GBBY和YRRGB，至少有兩種合并結(jié)果：GBYBRYRGB和YRRGGBBYB。對于每個顏色c來

41、說，其跨度L(c)等于最大位置和最小位置之差。例如，對于上面兩種合并結(jié)果，每個顏色的L(c)和所有L(c)的總和如圖9-8所示。圖9-8 每個顏色的L(c)和L(c)的總和你的任務(wù)是找一種合并方式，使得所有L(c)的總和最小。【分析】根據(jù)前面的經(jīng)驗，可以設(shè)d(i,j)表示兩個序列已經(jīng)分別移走了i和j個元素，還需要多少費用。等一下！什么叫“還需要多少費用”呢？本題的指標(biāo)函數(shù)（即需要最小化的函數(shù)）比較復(fù)雜。當(dāng)某顏色第一次出現(xiàn)在最終序列中時，并不知道它什么時候會結(jié)束；而某個顏色的最后一個元素已經(jīng)移到最終序列里時，又“忘記”了它是什么時候第一次出現(xiàn)的。怎么辦呢？如果記錄每個顏色的第一次出現(xiàn)位置，狀態(tài)會

42、變得很復(fù)雜，時間也無法承受，所以只能把在指標(biāo)函數(shù)的“計算方式”上想辦法：不是等到一個顏色全部移完之后再算，而是每次累加。換句話說，當(dāng)把一個顏色移到最終序列前，需要把所有“已經(jīng)出現(xiàn)但還沒結(jié)束”的顏色的L(c)值加1。更進(jìn)一步地，因為并不關(guān)心每個顏色的L(c)，所以只需要知道有多少種顏色已經(jīng)開始但尚未結(jié)束。例如，序列GBBY和YRRGB，分別已經(jīng)移走了1個和3個元素（例如，已經(jīng)合并成了YRRG）。下次再從序列2移走一個元素（即G）時，Y和G需要加1。下次再從序列1移走一個元素（它是B）時，只有Y需要加1（因為G已經(jīng)結(jié)束）。這樣，可以事先算出每個顏色在兩個序列中的開始和結(jié)束位置，就可以在動態(tài)規(guī)劃時在

43、O(1)時間內(nèi)計算出狀態(tài)d(i,j)中“有多少個顏色已經(jīng)出現(xiàn)但尚未結(jié)束”，從而在O(1)時間內(nèi)完成狀態(tài)轉(zhuǎn)移。狀態(tài)總是為O(nm)個，總時間復(fù)雜度也是O(nm)。最優(yōu)矩陣鏈乘。一個矩陣由n行m列共個數(shù)排列而成。兩個矩陣A和B可以相乘當(dāng)且僅當(dāng)A的列數(shù)等于B的行數(shù)。一個的矩陣乘以一個的矩陣等于一個的矩陣，運算量為mnp。矩陣乘法不滿足分配律，但滿足結(jié)合律，因此ABC既可以按順序(AB)C進(jìn)行，也可以按A(BC)進(jìn)行。假設(shè)A、B、C分別是，和的，則(AB)C的運算量為，A(BC)的運算量為。顯然第一種順序節(jié)省運算量。給出n個矩陣組成的序列，設(shè)計一種方法把它們依次乘起來，使得總的運算量盡量小。假設(shè)第i個

44、矩陣Ai是的?！痉治觥勘绢}任務(wù)是設(shè)計一個表達(dá)式。在整個表達(dá)式中，一定有一個“最后一次乘法”。假設(shè)它是第k個乘號，則在此之前已經(jīng)算出了和。由于P和Q的計算過程互不相干，而且無論按照怎樣的順序，P和Q的值都不會發(fā)生改變，因此只需分別讓P和Q按照最優(yōu)方案計算（最優(yōu)子結(jié)構(gòu)?。┘纯?。為了計算P的最優(yōu)方案，還需要繼續(xù)枚舉的“最后一次乘法”，把它分成兩部分。不難發(fā)現(xiàn)，無論怎么分，在任意時候，需要處理的子問題都形如“把Ai，Ai+1，Aj乘起來需要多少次乘法？”如果用狀態(tài)f(i, j)表示這個子問題的值，不難列出如下的狀態(tài)轉(zhuǎn)移方程：邊界為f(i, i)=0。上述方程有些特殊：記憶化搜索固然沒問題，但如果要寫成

45、遞推，無論按照i還是j的遞增或遞減順序均不正確。正確的方法是按照j-i遞增的順序遞推，因為長區(qū)間的值依賴于短區(qū)間的值。最優(yōu)三角剖分。對于一個n個頂點的凸多邊形，有很多種方法可以對它進(jìn)行三角剖分（triangulation），即用n-3條互不相交的對角線把凸多邊形分成n-2個三角形。為每個三角形規(guī)定一個權(quán)函數(shù)w(i, j, k)（如三角形的周長或3個頂點的權(quán)和），求讓所有三角形權(quán)和最大的方案?！痉治觥勘绢}和最優(yōu)矩陣鏈乘問題十分相似，但存在一個顯著不同：鏈乘表達(dá)式反映了決策過程，而剖分不反映決策過程。舉例來說，在鏈乘問題中，方案(A1A2)(A3(A4A5)只能是先把序列分成A1A2和A3A4A5

46、兩部分，而對于一個三角剖分，“第一刀”可以是任何一條對角線，如圖9-9所示。如果允許隨意切割，則“半成品”多邊形的各個頂點是可以在原多邊形中隨意選取的，很難簡潔定義成狀態(tài)，而“矩陣鏈乘”就不存在這個問題無論怎樣決策，面臨的子問題一定可以用區(qū)間表示。在這樣的情況下，有必要把決策的順序規(guī)范化，使得在規(guī)范的決策順序下，任意狀態(tài)都能用區(qū)間表示。定義d(i, j)為子多邊形i, i+1, j-1, j（ij）的最優(yōu)值，則邊i-j在最優(yōu)解中一定對應(yīng)一個三角形i-j-k（ikj），如圖9-10所示（注意頂點是按照逆時針編號的）。因此，狀態(tài)轉(zhuǎn)移方程為：時間復(fù)雜度為O(n3)，邊界為d(i,i+1)=0，原問題

47、的解為d(0,n-1)。圖9-9 難以簡潔表示的狀態(tài)圖9-10 定義的子多邊形例題9-9 切木棍（Cutting Sticks, UVa 10003）有一根長度為L（L1000）的棍子，還有n（n50）個切割點的位置（按照從小到大排列）。你的任務(wù)是在這些切割點的位置處把棍子切成n+1部分，使得總切割費用最小。每次切割的費用等于被切割的木棍長度。例如，L=10，切割點為2, 4, 7。如果按照2, 4, 7的順序，費用為10+8+6=24，如果按照4, 2, 7的順序，費用為10+4+6=20。【分析】設(shè)d(i,j)為切割小木棍ij的最優(yōu)費用，則d(i,j)=mind(i,k)+d(k,j) |

48、 ikj+aj-ai，其中最后一項aj-ai代表第一刀的費用。切完之后，小木棍變成ik和kj兩部分，狀態(tài)轉(zhuǎn)移方程由此可得。把切割點編號為1n，左邊界編號為0，右邊界編號為n+1，則答案為d(0,n+1)。狀態(tài)有O(n2)個，每個狀態(tài)的決策有O(n)個，時間復(fù)雜度為O(n3)。值得一提的是，本題可以用四邊形不等式優(yōu)化到O(n2)，有興趣的讀者請參見本書的配套算法競賽入門經(jīng)典訓(xùn)練指南或其他參考資料。例題9-10 括號序列（Brackets Sequence, NEERC 2001, UVa1626）定義如下正規(guī)括號序列（字符串）：空序列是正規(guī)括號序列。如果S是正規(guī)括號序列，那么(S)和S也是正規(guī)括

49、號序列。如果A和B都是正規(guī)括號序列，那么AB也是正規(guī)括號序列。例如，下面的字符串都是正規(guī)括號序列：()， ， ()， ()， ()， ()()，而如下字符串則不是正規(guī)括號序列：(， ， ， )(， ()。輸入一個長度不超過100的，由“(”、“)”、“”、“”構(gòu)成的序列，添加盡量少的括號，得到一個規(guī)則序列。如有多解，輸出任意一個序列即可?！痉治觥吭O(shè)串S至少需要增加d(S)個括號，轉(zhuǎn)移如下：如果S形如(S)或者S，轉(zhuǎn)移到d(S)。如果S至少有兩個字符，則可以分成AB，轉(zhuǎn)移到d(A)+d(B)。邊界是：S為空時d(S)=0，S為單字符時d(S)=1。注意(S, S, )S之類全部屬于第二種轉(zhuǎn)移，不

50、需要單獨處理。注意：不管S是否滿足第一條，都要嘗試第二種轉(zhuǎn)移，否則“”會轉(zhuǎn)移到“”，然后就只能加兩個括號了。當(dāng)然，上述“方程”只是概念上的，落實到程序時要改成子串在原串中的起始點下標(biāo)，即用d(i,j)表示子串Sij至少需要添加幾個括號。下面是遞推寫法，比記憶化寫法要快好幾倍，而且代碼更短。請讀者注意狀態(tài)的枚舉順序：void dp() for(int i = 0; i = 0; i-)for(int j = i+1; j n; j+) dij = n;if(match(Si, Sj) dij = min(dij, di+1j-1);for(int k = i; k j) return ;if(i

51、 = j) if(Si = ( | Si = ) printf();else printf();return; int ans = dij;if(match(Si, Sj) & ans = di+1j-1) printf(%c, Si); print(i+1, j-1); printf(%c, Sj);return; for(int k = i; k j; k+)if(ans = dik + dk+1j) print(i, k); print(k+1, j);return; 本題唯一的陷阱是：輸入串可能是空串，因此不能用scanf(%s, s)的方式輸入，只能用getchar、fgets或者g

52、etline。例題9-11 最大面積最小的三角剖分（Minimax Triangulation, ACM/ICPC NWERC 2004, UVa1331）三角剖分是指用不相交的對角線把一個多邊形分成若干個三角形。如圖9-11所示是一個六邊形的幾種不同的三角剖分。圖9-11 六邊形的不同三角部分輸入一個簡單m（2m50）邊形，找一個最大三角形面積最小的三角剖分。輸出最大三角形的面積。在圖9-11的5個方案中，最左邊（即左下角）的方案最優(yōu)?！痉治觥勘绢}的程序?qū)崿F(xiàn)要用到一些計算幾何的知識，不過基本思想是清晰的：首先考慮凸多邊形的簡單情況。和“最優(yōu)三角剖分”一樣，設(shè)d(i,j)為子多邊形i,i+1,

53、j-1,j（ij）的最優(yōu)解，則狀態(tài)轉(zhuǎn)移方程為d(i,j)= minS(i,j,k), d(i,k), d(k,j) | ikj，其中S(i,j,k)為三角形i-j-k的面積?；氐皆}。需要保證邊i-j是對角線如何判斷i-j是否為多邊形的對角線？限于篇幅，本書沒有對計算幾何進(jìn)行專門討論，請讀者參考算法競賽入門經(jīng)典訓(xùn)練指南的幾何部分。（唯一的例外是i=0且j=n-1），具體方法是當(dāng)邊i-j不滿足條件時直接設(shè)d(i,j)為無窮大，其他部分和凸多邊形的情形完全一樣。9.4.2 樹上的動態(tài)規(guī)劃樹的最大獨立集。對于一棵n個結(jié)點的無根樹，選出盡量多的結(jié)點，使得任何兩個結(jié)點均不相鄰（稱為最大獨立集），然后輸入

54、n-1條無向邊，輸出一個最大獨立集（如果有多解，則任意輸出一組）?！痉治觥坑胐(i)表示以i為根結(jié)點的子樹的最大獨立集大小。此時需要注意的是，本題的樹是無根的：沒有所謂的“父子”關(guān)系，而只有一些無向邊。沒關(guān)系，只要任選一個根r，無根樹就變成了有根樹，上述狀態(tài)定義也就有意義了。結(jié)點i只有兩種決策：選和不選。如果不選i，則問題轉(zhuǎn)化為了求出i的所有兒子的d值再相加；如果選i，則它的兒子全部不能選，問題轉(zhuǎn)化為了求出i的所有孫子的d值之和。換句話說，狀態(tài)轉(zhuǎn)移方程為：其中，gs(i)和s(i)分別為i的孫子集合與兒子集合，如圖9-12所示。代碼應(yīng)如何編寫呢？上面的方程涉及“枚舉結(jié)點i的所有兒子和所有孫子”

55、，頗為不便。其實可以換一個角度來看：不從i找s(i)和gs(i)的元素，而從s(i)和gs(i)的元素找i。換句話說，當(dāng)計算出一個d(i)后，用它去更新i的父親和祖父結(jié)點的累加值和。這樣一來，每個結(jié)點甚至不必記錄其子結(jié)點有哪些，只需記錄父結(jié)點即可。這就是前面提過的“刷表法”。不過這個問題還有另外一種解法，在實踐中更加常用，將在例題部分介紹。樹的重心（質(zhì)心）。對于一棵n個結(jié)點的無根樹，找到一個點，使得把樹變成以該點為根的有根樹時，最大子樹的結(jié)點數(shù)最小。換句話說，刪除這個點后最大連通塊（一定是樹）的結(jié)點數(shù)最小?！痉治觥亢蜆涞淖畲螵毩⒓瘑栴}類似，先任選一個結(jié)點作為根，把無根樹變成有根樹，然后設(shè)d(i

56、)表示以i為根的子樹的結(jié)點個數(shù)。不難發(fā)現(xiàn)。程序?qū)崿F(xiàn)也很簡單：只需要一次DFS，在無根樹轉(zhuǎn)有根樹的同時計算即可，連記憶化都不需要因為本來就沒有重復(fù)計算。那么，刪除結(jié)點i后，最大的連通塊有多少個結(jié)點呢？結(jié)點i的子樹中最大的有maxd(j)個結(jié)點，i的“上方子樹”中有n-d(i)個結(jié)點，如圖9-13所示。這樣，在動態(tài)規(guī)劃的過程中就可以順便找出樹的重心了。圖9-12 結(jié)點i的gs(i)（淺灰色）和s(i)（深灰色）圖9-13 樹中的結(jié)點分布樹的最長路徑（最遠(yuǎn)點對）。對于一棵n個結(jié)點的無根樹，找到一條最長路徑。換句話說，要找到兩個點，使得它們的距離最遠(yuǎn)?！痉治觥亢蜆涞闹匦膯栴}一樣，先把無根樹轉(zhuǎn)成有根樹。

57、對于任意結(jié)點i，經(jīng)過i的最長路就是連接i的兩棵不同子樹u和v的最深葉子的路徑，如圖9-14所示。圖9-14 子樹u和v的最深葉子路徑設(shè)d(i)表示根為結(jié)點i的子樹中根到葉子的最大距離，不難寫出狀態(tài)轉(zhuǎn)移方程：。對于每個結(jié)點i，把所有子結(jié)點的d(j)都求出來之后，設(shè)d值前兩大的結(jié)點為u和v，則d(u)+d(v)+2就是所求。本題還有一個不用動態(tài)規(guī)劃的解法：隨便找一個結(jié)點u，用DFS求出u的最遠(yuǎn)結(jié)點v，然后再用一次DFS求出v的最遠(yuǎn)結(jié)點w，則v-w就是最長路徑。結(jié)合上述兩個問題的解法，可以解決下面的問題：對于一棵n個結(jié)點的無根樹，求出每個結(jié)點的最遠(yuǎn)點，要求時間復(fù)雜度為O(n)。這個問題留給讀者思考。

58、例題9-12 工人的請愿書（Another Crisis, UVa 12186）某公司里有一個老板和n（n105）個員工組成樹狀結(jié)構(gòu)，除了老板之外每個員工都有唯一的直屬上司。老板的編號為0，員工編號為1n。工人們（即沒有直接下屬的員工）打算簽署一項請愿書遞給老板，但是不能跨級遞，只能遞給直屬上司。當(dāng)一個中級員工（不是工人的員工）的直屬下屬中不小于T%的人簽字時，他也會簽字并且遞給他的直屬上司。問：要讓公司老板收到請愿書，至少需要多少個工人簽字？【分析】設(shè)d(u)表示讓u給上級發(fā)信最少需要多少個工人。假設(shè)u有k個子結(jié)點，則至少需要c=(kT-1)/100+1個直接下屬發(fā)信才行。把所有子結(jié)點的d值

59、從小到大排序，前c個加起來即可。最終答案是d(0)。因為要排序，算法的時間復(fù)雜度為O(nlogn)。動態(tài)規(guī)劃部分代碼如下：vector sonsmaxn; /sonsi為結(jié)點i的子列表int dp(int u) if(sonsu.empty() return 1;int k = sonsu.size();vector d;for(int i = 0; i k; i+) d.push_back(dp(sonsui);sort(d.begin(), d.end();int c = (k*T - 1) / 100 + 1;int ans = 0;for(int i = 0; i d(v,1)且f(v

60、,0)=0，則f(u,0)=0）。例題9-14 完美的服務(wù)（Perfect Service, ACM/ICPC Kaoshiung 2006, UVa1218）有n（n10000）臺機(jī)器形成樹狀結(jié)構(gòu)。要求在其中一些機(jī)器上安裝服務(wù)器，使得每臺不是服務(wù)器的計算機(jī)恰好和一臺服務(wù)器計算機(jī)相鄰。求服務(wù)器的最少數(shù)量。如圖9-15所示，圖9-15（a）是非法的，因為4同時和兩臺服務(wù)器相鄰，而6不與任何一臺服務(wù)器相鄰。而圖9-15（b）是合法的。（a）（b）圖9-15 非法與合法的樹狀結(jié)構(gòu)【分析】有了前面的經(jīng)驗，這次仍然按照每個結(jié)點的情況進(jìn)行分類。d(u,0)：u是服務(wù)器，則每個子結(jié)點可以是服務(wù)器也可以不是。