浙江大學(xué)acm程序設(shè)計競賽動態(tài)規(guī)劃講義

前言本文只是個人對動態(tài)規(guī)劃的一些見解,理論性并不一定能保證正確,有不足和缺漏之處請諒解和及時地指出.第1頁/共74頁第一頁，共75頁。動態(tài)規(guī)劃

是信息學(xué)競賽中選手必須熟練掌握的一種算法,他以其多元性廣受出題者的喜愛.動態(tài)規(guī)劃第2頁/共74頁第二頁，共75頁。目錄什么是動態(tài)規(guī)劃狀態(tài)階段決策一種確立狀態(tài)的方法兩種簡單的動規(guī)武器三種特殊的動態(tài)規(guī)劃第3頁/共74頁第三頁，共75頁。什么是動態(tài)規(guī)劃在學(xué)習(xí)動態(tài)規(guī)劃之前你一定學(xué)過搜索.那么搜索與動態(tài)規(guī)劃有什么關(guān)系呢?我們來下面的一個例子.back第4頁/共74頁第四頁，共75頁。數(shù)字三角形給你一個數(shù)字三角形,形式如下:12345678910找出從第一層到最后一層的一條路,使得所經(jīng)過的權(quán)值之和最小或者最大.back第5頁/共74頁第五頁，共75頁。數(shù)字三角形無論對與新手還是老手，這都是再熟悉不過的題了，很容易地，我們寫出狀態(tài)轉(zhuǎn)移方程：f(i,j)=a[i,j]+min{f(i-1,j)+f(i-1,j+1)}對于動態(tài)規(guī)劃算法解決這個問題，我們根據(jù)狀態(tài)轉(zhuǎn)移方程和狀態(tài)轉(zhuǎn)移方向，比較容易地寫出動態(tài)規(guī)劃的循環(huán)表示方法。但是，當(dāng)狀態(tài)和轉(zhuǎn)移非常復(fù)雜的時候，也許寫出循環(huán)式的動態(tài)規(guī)劃就不是那么簡單了。解決方法：back記憶化搜索第6頁/共74頁第六頁，共75頁。記憶化搜索我們嘗試從正面的思路去分析問題，如上例，不難得出一個非常簡單的遞歸過程

:f1:=f(i-1,j+1);f2:=f(i-1,j);iff1>f2thenf:=f1+a[i,j]elsef:=f2+a[i,j];顯而易見，這個算法就是最簡單的搜索算法。時間復(fù)雜度為2n，明顯是會超時的。分析一下搜索的過程，實際上，很多調(diào)用都是不必要的，也就是把產(chǎn)生過的最優(yōu)狀態(tài)，又產(chǎn)生了一次。為了避免浪費(fèi)，很顯然，我們存放一個opt數(shù)組：

back第7頁/共74頁第七頁，共75頁。記憶化搜索Opt[i,j]-每產(chǎn)生一個f(i,j)，將f(i,j)的值放入opt中，以后再次調(diào)用到f(i,j)的時候，直接從opt[i,j]來取就可以了。于是動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程被直觀地表示出來了，這樣節(jié)省了思維的難度，減少了編程的技巧，而運(yùn)行時間只是相差常數(shù)的復(fù)雜度，而且在相當(dāng)多的情況下，遞歸算法能更好地避免浪費(fèi)，在比賽中是非常實用的.記憶化的功效back第8頁/共74頁第八頁，共75頁。動態(tài)規(guī)劃的實質(zhì)可以看出動態(tài)規(guī)劃的實質(zhì)就是這也就是為什么我們常說動態(tài)規(guī)劃必須滿足重疊子問題的原因.記憶化,正符合了這個要求.記憶化搜索第9頁/共74頁第九頁，共75頁。狀態(tài)階段決策或許有一種對動態(tài)規(guī)劃的簡單稱法,叫分階段決策.其實我認(rèn)為這個稱法并不是很能讓人理解.那么下面我們來看看階段,狀態(tài),決策這三者間得關(guān)系吧.back第10頁/共74頁第十頁，共75頁。狀態(tài)階段決策狀態(tài)是表現(xiàn)出動態(tài)規(guī)劃核心思想的一個東西.而分階段決策這個東西有似乎沒有提到狀態(tài),這是不科學(xué)的.階段,有些題目并不一定表現(xiàn)出一定的階段性.數(shù)字三角形的階段就是每一層.這里我們引入一個概念---以前狀態(tài).但階段不是以前狀態(tài),狀態(tài)是階段的表現(xiàn)形式.數(shù)字三角形的以前狀態(tài)就是當(dāng)前層的前一層.那什么是決策呢?我們看看下面一張圖就知道了.back第11頁/共74頁第十一頁，共75頁。決策當(dāng)前狀態(tài)以前狀態(tài)決策顯然,從上圖可以看出,當(dāng)前狀態(tài)通過決策,回到了以前狀態(tài).可見決策其實就是狀態(tài)之間的橋梁。而以前狀態(tài)也就決定了當(dāng)前狀態(tài)的情況。數(shù)字三角形的決策就是選擇相鄰的兩個以前狀態(tài)的最優(yōu)值。back第12頁/共74頁第十二頁，共75頁。動規(guī)的要訣－狀態(tài)我們一般在動規(guī)的時候所用到的一些數(shù)組，也就是用來存儲每個狀態(tài)的最優(yōu)值的。我們就從動態(tài)規(guī)劃的要訣，也就是核心部分“狀態(tài)”開始，來逐步了解動態(tài)規(guī)劃。back第13頁/共74頁第十三頁，共75頁。攔截導(dǎo)彈攔截導(dǎo)彈（Noip2002）某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈依次飛來的高度，計算這套系統(tǒng)最多能攔截多少導(dǎo)彈。第14頁/共74頁第十四頁，共75頁。攔截導(dǎo)彈狀態(tài)的表示－f[i]，表示當(dāng)?shù)趇個導(dǎo)彈必須選擇時，前i個導(dǎo)彈最多能攔截多少。每個導(dǎo)彈有一定的高度，當(dāng)前狀態(tài)就是以第i個導(dǎo)彈為最后一個打的導(dǎo)彈。以前狀態(tài)就是在這個導(dǎo)彈以前打的那個導(dǎo)彈。顯然這是十分能夠體現(xiàn)狀態(tài)間的聯(lián)系的題目。back第15頁/共74頁第十五頁，共75頁。最長公共子串給出兩個字符串序列。求出這樣的一個最長的公共子串：子串中的每個字符都能在兩個原串中找到，而且每個字符的順序和原串中的順序一致。第16頁/共74頁第十六頁，共75頁。交錯匹配交錯匹配（最長公共子串的改編）給你兩排數(shù)字,只能將兩排中數(shù)字相同的兩個位置相連,而每次相連必須有兩個匹配形成一次交錯,交錯的連線不能再和別的交錯連線有交點.問這兩排數(shù)字最多能形成多少個交錯匹配.233241513510312324121553狀態(tài)的表示－f[i,j]表示前i個第一排的數(shù)字和前j個第二排的數(shù)字搭配的最優(yōu)值。當(dāng)前的狀態(tài)就是當(dāng)前你枚舉到的一組交錯的后面兩個位置.例如上圖中當(dāng)前狀態(tài)是3和1(第一組交錯),枚舉他的以前狀態(tài)就有13.這樣在13之前會有一個最優(yōu)值存在,因此可以由此得到31的最優(yōu)值.back第17頁/共74頁第十七頁，共75頁。買車票買車票(Ural1031)Ekaterinburg城到Sverdlovsk城有直線形的鐵路線。

兩城之間還有其他一些?？空?總站數(shù)為N。

各站按照離Ekaterinburg城的距離編號。

Ekaterinburg城編號為1，Sverdlovsk城編號為N。back第18頁/共74頁第十八頁，共75頁。買車票某兩站之間車票價格由這兩站的距離X決定.

當(dāng)0<X<=L1時，票價為C1元.

當(dāng)L1<X<=L2時，票價為C2元.

當(dāng)L2<X<=L3時，票價為C3元.當(dāng)兩站距離大于L3時沒有直達(dá)票，所以有時候要買幾次票做幾次車才行。比如，在上面的例圖中，2-6沒有直達(dá)票，有幾種買票方法可以從2-6，其中一種是買C2元的2-3車票，再買C3元的3-6車票。back第19頁/共74頁第十九頁，共75頁。買車票給定起點站和終點站還有L1,L2,L3,C1,C2,C3，求出要從起點到終點最少要花多少錢.怎么辦確定題目的當(dāng)前狀態(tài)與以前狀態(tài)!back第20頁/共74頁第二十頁，共75頁。買車票當(dāng)前狀態(tài)以前狀態(tài)當(dāng)前所在的某個車站這一題的以前狀態(tài)其實只有3種.即滿足3種距離(收費(fèi))情況的3個車站.要知道這3個車站可以先做一個預(yù)處理.顯然這3個車站在滿足距離限制的條件下應(yīng)該越遠(yuǎn)越好.back第21頁/共74頁第二十一頁，共75頁。買車票預(yù)處理很容易想出一個N^2的預(yù)處理,但是那樣是會超時的.由于盡量要讓車站離得遠(yuǎn)(費(fèi)用是一樣的啊)因此在每種收費(fèi)情況下,每個車站的以前狀態(tài)車站一定是遞增的序列.這里是只要O(N)的程序:forj:=1to3dobegink:=en-1;fori:=endowntobedobeginwhile(way[i]-way[k]<=l[j])and(k>=be)dodec(k);p[i][j]:=k+1;end;end;

數(shù)組P[i][j]表示的是I狀態(tài)的第j種以前狀態(tài).back第22頁/共74頁第二十二頁，共75頁。買車票動態(tài)規(guī)劃的部分fori:=be+1toendo{枚舉當(dāng)前狀態(tài)}begincost[i]:=maxlongint;forj:=1to3do{枚舉以前狀態(tài)}beginif(p[i][j]<>i)and(cost[i]>cost[p[i][j]]+c[j])thencost[i]:=cost[p[i][j]]+c[j];end;end;back第23頁/共74頁第二十三頁，共75頁。動規(guī)的要訣－狀態(tài)有時候當(dāng)前狀態(tài)確定后,以前狀態(tài)就已經(jīng)確定,則無需枚舉.back第24頁/共74頁第二十四頁，共75頁。Tom的煩惱Tom是一個非常有創(chuàng)業(yè)精神的人，由于大學(xué)學(xué)的是汽車制造專業(yè)，所以畢業(yè)后他用有限的資金開了一家汽車零件加工廠，專門為汽車制造商制造零件。由于資金有限，他只能先購買一臺加工機(jī)器。現(xiàn)在他卻遇到了麻煩，多家汽車制造商需要他加工一些不同零件（由于廠家和零件不同，所以給的加工費(fèi)也不同），而且不同廠家對于不同零件的加工時間要求不同（有些加工時間要求甚至是沖突的，但開始和結(jié)束時間相同不算沖突）。Tom當(dāng)然希望能把所有的零件都加工完，以得到更多的加工費(fèi)，但當(dāng)一些零件的加工時間要求有沖突時，在某個時間內(nèi)他只能選擇某種零件加工（因為他只有一臺機(jī)器），為了賺得盡量多的加工費(fèi)，Tom不知如何進(jìn)行取舍。第25頁/共74頁第二十五頁，共75頁。Tom的煩惱Tom的煩惱按結(jié)束時間排序，枚舉結(jié)束時間作為當(dāng)前狀態(tài),以前狀態(tài)就是該結(jié)束時間對應(yīng)的起始時間，這是已經(jīng)確定的.back第26頁/共74頁第二十六頁，共75頁。文字游戲文字游戲(fairfox邀請賽1)

給你一份單詞表，和一個句子。求出該句子能有多少中不同的劃分方法.例如:

單詞是abcdabcd

句子是abcd

他共有4種完全劃分方案:ab/cda/b/c/da/b/cdab/c/d;

當(dāng)前狀態(tài)就是單詞在句子中向后靠的位置,以前狀態(tài)就是確定這個單詞位置以后,除掉這個單詞長度后的一個位置.狀態(tài)轉(zhuǎn)移方程是:F[i]:=F[i]+F[i-length(word[j])]IOI中有一題《前綴》也是類似的題目.第27頁/共74頁第二十七頁，共75頁。決策中的定量狀態(tài)轉(zhuǎn)移方程的構(gòu)造無疑是動態(tài)規(guī)劃過程中最重要的一步,也是最難的一步.對于大多數(shù)的動態(tài)規(guī)劃,尋找狀態(tài)轉(zhuǎn)移方程有一條十分高效的通道,就是尋找變化中的不變量.定量處理的過程也就是決策實施的過程.尋找定量back第28頁/共74頁第二十八頁，共75頁。尋找定量最佳加法表達(dá)式有一個由1..9組成的數(shù)字串.問如果將m個加號插入到這個數(shù)字串中.使得所形成的算術(shù)表達(dá)式的值最小.Problem或許你不明白我在說什么,那么我們通過題目來說明吧back第29頁/共74頁第二十九頁，共75頁。最佳加法表達(dá)式這一題中的定量是什么呢?因為是添入加號,那么添完加號后,表達(dá)式的最后一定是個數(shù)字串,這就是定量.從這里入手,不難發(fā)現(xiàn)可以把以前狀態(tài)認(rèn)為是在前i個字符中插入k-1個加號(這里的i是當(dāng)作決策在枚舉),然后i+1到最后一位一定是整個沒有被分割的數(shù)字串,第k個加號就添在i與i+1個數(shù)字之間.這樣就構(gòu)造出了整個數(shù)字串的最優(yōu)解.而至于前i個字符中插入k-1個加號,這又回到了原問題的形式,也就是回到了以前狀態(tài),所以狀態(tài)轉(zhuǎn)移方程就能很快的構(gòu)造出來了.back第30頁/共74頁第三十頁，共75頁。最佳加法表達(dá)式用f[i,j],表示的是在前i個字符中插入j個加號能達(dá)到的最小值,最后的答案也就是F[length(s),m].于是就有一個動規(guī)的方程:F[i,j]:=min(f[i,j],f[k,j-1]+num[k+1,i])num[k+1,i]表示k+1位到i位所形成的數(shù)字.這里顯然是把加號插入了第k+1個位置上.知道了這一題怎么做以后,乘積最大的一題也是完全一樣的形式,誰還會去用搜索?back第31頁/共74頁第三十一頁，共75頁。定量現(xiàn)在大概大家已經(jīng)了解了定量是什么,那么我們下面通過幾道題目來了解一下定量的威力.back第32頁/共74頁第三十二頁，共75頁。游戲游戲(Noip2003普及組)這一題的描述簡單說一下:在一個圈的周圍有n個石子,將他們劃分成m堆(每堆中的石子必須連續(xù)相鄰),每一堆石子計算出他們的總重量mod10的值,然后將這些值相乘,求得到的結(jié)果最大最小值是多少.back第33頁/共74頁第三十三頁，共75頁。游戲這一題作者其實是根據(jù)最佳加法表達(dá)式改編的.但是他加了一個在圈上的條件,怎么辦呢?尋找定量!back第34頁/共74頁第三十四頁，共75頁。游戲可想而知,因為至少要分成1堆,那么至少有兩個石子之間是會被分隔開的.這就是定量!當(dāng)劃分?jǐn)?shù)>1時,一定有兩個相鄰石子被劃分到不同的堆里去!于是這個圈被這樣的理解斷成了一條線,解法就和最佳加法表達(dá)式一樣了.當(dāng)然這個斷開的位置是需要枚舉的,然后保留下一個最優(yōu)值.顯然這個斷開的操作對整個過程沒有影響,因為這是必然的情況,這是定量!back第35頁/共74頁第三十五頁，共75頁。最優(yōu)三角形劃分問題描述給定一具有N（N<50）個頂點(從1到N編號）的凸多邊形，每個頂點的權(quán)均已知。問如何把這個凸多邊形劃分成N-2個互不相交的三角形，使得這些三角形頂點的權(quán)的乘積之和最小？

back第36頁/共74頁第三十六頁，共75頁。最優(yōu)三角形劃分這一題大概搜都是十分麻煩的,可是這一題Dp的話,比搜索要容易實現(xiàn)和容易理解得多.先得表示一下狀態(tài),我們用f[i,j]表示以第i個點開頭,順時針長度為j的一塊子多邊形.如上圖中f[1,5]表示的子多邊形(黑色虛線劃開)back第37頁/共74頁第三十七頁，共75頁。最優(yōu)三角形劃分如果沒有紅色虛線的部分,或許你會認(rèn)為決策應(yīng)該是枚舉子多邊形內(nèi)的兩點連線,然后分成兩個子多邊形.這顯然是不行的,因為計算機(jī)已經(jīng)無法再表示分割出來的子多邊形了(不能用f[i,j]來表示了).back第38頁/共74頁第三十八頁，共75頁。最優(yōu)三角形劃分那么我們該如何決策呢?尋找定量!顯然可以發(fā)現(xiàn),f[i,j]表示的子多邊形有一條邊是在內(nèi)部的(黑色虛線),而這一條邊在該子多邊形內(nèi)必定屬于某個三角形,因為我們選擇了該子多邊形作為一種狀態(tài),那么就一定存在那條虛線黑邊,所以一定存在所說的三角形.于是我們枚舉這個三角形的另外一個點在子多邊形的位置,則可以把子問題還原到原問題(因為該三角形把多邊形劃成了兩個可以用表示的多邊形和一個三角形).這些再次分割出的子多邊形就是以前狀態(tài),而剛才的多邊形則是當(dāng)前狀態(tài).back第39頁/共74頁第三十九頁，共75頁。定量其實定量的作用就是為了寫出狀態(tài)轉(zhuǎn)移方程,即讓人能迅速找出狀態(tài)之間的關(guān)系(決策).通過定量的處理,當(dāng)前狀態(tài)又回到了以前狀態(tài),選手就可以知道,這一題就是要用動態(tài)規(guī)劃來求解了.back第40頁/共74頁第四十頁，共75頁。定量我們來看看剛才的一些題目的定量.交錯匹配:一定存在最后一組交錯(這好像是廢話),所以枚舉這個最后的交錯的位置作為狀態(tài),這樣就回到以前狀態(tài).買車票:定量1:一定有最后一個車站(這個作為狀態(tài));定量2:某個車站一定是由某個前面的車站到達(dá)的.(導(dǎo)彈攔截也是這樣)數(shù)字三角形:某個點一定是由他上面的相鄰兩點到達(dá)的.(過河卒也是這樣)定量很不錯啊!第41頁/共74頁第四十一頁，共75頁。動態(tài)規(guī)劃的武器在動規(guī)的操作過程中,或者是操作過程前,有一些很常用的武器,這里簡要介紹兩種:排序填鴨back第42頁/共74頁第四十二頁，共75頁。排序武器一:排序遇到過很多需要排序的動態(tài)規(guī)劃題目,如果不排序,動規(guī)的思想很難體現(xiàn).back第43頁/共74頁第四十三頁，共75頁。Tom的煩惱Tom的煩惱這是大家熟知的一題,如果不排序的話,復(fù)雜度便是N^2,按起始時間排序復(fù)雜度也是N^2,二按結(jié)束時間排序之后復(fù)雜度降為了NlogN.back第44頁/共74頁第四十四頁，共75頁。巴比倫塔巴比倫塔問題描述:

有很多的不同種類的立方體(長寬高不同),每一類有無限多個.將他們一層層的疊加起來,要求上面的一塊立方體的下底面一定要比下面的一塊立方體的上底面要小,就是長和寬都要小于.問最多能建成多高的塔.back第45頁/共74頁第四十五頁，共75頁。巴比倫塔經(jīng)過研究可以發(fā)現(xiàn),每一種類的立方體有3種不同的擺放方式,而每種擺放方式最多用1次,所以可以分離出3*N塊“不同”的立方體,接下來,或許你仍然不知道如何動規(guī),那么就試試排序.列出所有的石塊的所有擺放方式xi,yi,zi.必須全部保證xi<yi或者xi>yi.然后按關(guān)鍵字xi,yi,zi的大小順序排序.這樣就可以進(jìn)行十分簡單的類似與導(dǎo)彈攔截的一個動態(tài)規(guī)劃的處理了.限制條件是xi和yi,代價值是zi(高度).back第46頁/共74頁第四十六頁，共75頁?；┗?上海2002)題目的大意是給出一個矩陣,如:對于所給出的矩陣找出一條最長的遞減鏈,滿足鏈中相鄰的兩個元素間都是在矩陣中相鄰的.上圖中所給出的矩陣中的最長鏈?zhǔn)?234……25.back第47頁/共74頁第四十七頁，共75頁?；τ谟薪o出的數(shù)字進(jìn)行遞減排序,然后兩重循環(huán)就搞定問題.動態(tài)轉(zhuǎn)移方程是:F[i]:=max(F[i],F[j]+1);

滿足條件是i與j在原矩陣中相鄰.試想,如果你不知道要排序,你能想到這題是用動態(tài)規(guī)劃嗎?back第48頁/共74頁第四十八頁，共75頁。填鴨武器二:填鴨這個思想帶有枚舉的感覺.就是開個大數(shù)組,把代價值一個個填進(jìn)去.back第49頁/共74頁第四十九頁，共75頁。硬幣問題硬幣問題（經(jīng)典問題）就是給出n種硬幣的面值,問面值M有多少種不同的表示方法.

動態(tài)轉(zhuǎn)移方程是F[i]:=F[i]+F[I-cost[j]].當(dāng)前狀態(tài)是i,以前狀態(tài)是i-cost[j].多米諾骨牌（某題的簡化）有N張多米諾骨牌,每張的兩端有兩個數(shù)字,范圍在1..6之間.每張骨牌可以正放,也可以反放.求出一種擺放的情況,使得所有的骨牌上端數(shù)字之和與下端數(shù)字之和的差值最小.求出最小差值.back第50頁/共74頁第五十頁，共75頁。多米諾骨牌可以這么考慮這個問題:我們把每一個骨牌的上下差值記下。接下來的任務(wù)便是將這些值分成兩組，使得他們的和的差值最小。動規(guī)過程如下：f[0]:=true;fori:=1tondoforj:=sumdowntoa[i]dof[j]:=f[j]orf[j-a[i]];Sum表示所有差值的和.a[i]表示第i塊骨牌的差值.J是當(dāng)前狀態(tài),j-a[i]是以前狀態(tài).f[j]表示j這個差值能否通過組合得到。接下來的程序就不用我多說了。back第51頁/共74頁第五十一頁，共75頁。商店購物商店購物(IOI)

這一題更是需要開一個五維bool型數(shù)組.還需要通過遞歸求出組合形式.動規(guī)的方程我就不寫了.back第52頁/共74頁第五十二頁，共75頁。動態(tài)規(guī)劃的武器講完了比較實用的兩種種動規(guī)的武器之后,我們來看看一些大家可能不太會做的動規(guī)類型第53頁/共74頁第五十三頁，共75頁。特殊的動規(guī)這里我講講三種特殊的動態(tài)規(guī)劃:圖狀動規(guī),樹狀動規(guī),二次動規(guī).back第54頁/共74頁第五十四頁，共75頁。圖狀動規(guī)城堡某國聰明美麗的公主要找一位如意郎君，她希望未來的夫君是一個聰明善良，節(jié)儉但又不吝嗇的人。為了找到理想的人選，她的爸爸—國王，給她修建了一座城堡，這個城堡有很多房間，房間之間有走廊連接，但每進(jìn)入一個房間必須要花費(fèi)一定數(shù)量的錢幣，公主就在某個房間中等待。開始，國王給每個候選人一樣多的錢幣，候選人從同一個地點出發(fā)，直到找到美麗的公主為止，如果這時哪個人找到了公主，并且錢幣剛好用完，那么他將會贏得公主的芳心。back第55頁/共74頁第五十五頁，共75頁。城堡乍看此題,似乎就是搜沒得說了,是嗎?如果告訴你這一題是動態(tài)規(guī)劃的話,你會怎么做???狀態(tài)是什么動態(tài)轉(zhuǎn)移方程是什么???back第56頁/共74頁第五十六頁，共75頁。城堡既然是問我們能不能到達(dá),所以想想就應(yīng)該知道,動規(guī)的數(shù)組是bool型的.一開始時,只有出發(fā)的房間記為true.但是,并不是以每個房間作為狀態(tài),因為還存在一個把錢用光的問題.到達(dá)同一個房間時,如果剩余的錢不一樣,也就會有不同的決策.所以狀態(tài)就是在剩余j個錢幣的時候能否到達(dá)第i個房間.用f[i,j]來表示.back第57頁/共74頁第五十七頁，共75頁。圖狀動規(guī)于是動態(tài)轉(zhuǎn)移方程也就出來了f[i,j]:=f[i,j]orf[k,j+c[i]]K表示的是和I連接的一個房間,c[i]表示進(jìn)入I號房間的花費(fèi).back第58頁/共74頁第五十八頁，共75頁。樹狀動規(guī)沒有上司的晚會某公司要舉辦一次晚會，但是為了使得晚會的氣氛更加活躍，每個參加晚會的人都不希望在晚會中見到他的上司，要不然他們會很掃興。現(xiàn)在已知每個人的活躍指數(shù)和上司關(guān)系（當(dāng)然不可能存在環(huán)），求邀請哪些人來能使得晚會的總活躍指數(shù)最大。back第59頁/共74頁第五十九頁，共75頁。沒有上司的晚會按照要求構(gòu)建一張關(guān)系圖，可見這是一棵樹。對于這類最值問題，向來是用動態(tài)規(guī)劃求解的。任何一個點的取舍可以看作一種決策，那么狀態(tài)就是在某個點取的時候或者不取的時候，以他為跟的子樹能有的最大活躍總值。分別可以用f[i,1]和f[i,0]表示。back第60頁/共74頁第六十頁，共75頁。沒有上司的晚會當(dāng)這個點取的時候，他的所有兒子都不能取，所以f[i,1]:=sum(f[j,0],j為i的兒子)＋i的權(quán)值。不取的時候，他的所有兒子取不取無所謂，不過當(dāng)然應(yīng)該取價值最大的一種情況。所以f[i,0]:=sum(max(f[j,1],f[j,0]),j為i的i兒子）。這就是樹狀動規(guī)的基本形態(tài)。back第61頁/共74頁第六十一頁，共75頁。二次動規(guī)在動規(guī)的基礎(chǔ)上再進(jìn)行動規(guī)，就叫做二次動規(guī)。買票有一座n層的樓房，某個人要到第n層的任何一個房間買票。每層樓都有m個房間。而如果要到第i層的第j個房間買票，那么必須先在第i-1層的第j個房間買票或者在第i層的與這個房間相鄰的房間買過票才行.而每個房間所要收取的票費(fèi)是不同的,給定每個房間內(nèi)買票需要的費(fèi)用,問要在第n層的任意一間房間內(nèi)買到票的最小消費(fèi)是多少.back第62頁/共74頁第六十二頁，共75頁。買票顯然不能寫這樣的狀態(tài)轉(zhuǎn)移方程:f[i,j]:=min(f[i-1,j],f[i,j-1],f[i,j+1])+w[j].因為無法有一種處理順序使得在f[i,j]之前同時求得f[i,j-1]和f[i,j+1]的最優(yōu)值.所以動規(guī)分兩次進(jìn)行.第一次用狀態(tài)轉(zhuǎn)移方程f[i,j]:=min(f[i,j-1],f[i-1,j])+w[i]求出一個不一定是最優(yōu)的解.再用f[i,j]:=min(f[i,j],f[i,j+1],jfromm-1downto1)+w[i]求出最終的最優(yōu)解,可以證明這樣的能夠求出真正的最優(yōu)解.要注意的是這兩次動規(guī)不能分開做,而要在處理每一層的時候都要做,要不然顯然無法求得最優(yōu)值。back第63頁/共74頁第六十三頁，共75頁。綜合題網(wǎng)絡(luò)（Ural1056,求樹的中心）題目大意是：有一棵有N個結(jié)點的樹，給出每個結(jié)點的父親（即給出這棵樹），邊的權(quán)都是1。每個結(jié)點延樹的邊可以走到樹的任意一個結(jié)點，令A(yù)i為第i個結(jié)點最遠(yuǎn)能走的距離，求出Ai最小的結(jié)點有哪些。如有多個最小的Ai，則都要輸出。這里N<=10000

back第64頁/共74頁第六十四頁，共75頁。網(wǎng)絡(luò)枚舉每個點，然后DFS復(fù)雜度O(N2)，超時是顯然的事情?？梢园l(fā)現(xiàn)其實有很多DFS都重復(fù)做了同樣的工作，產(chǎn)生了浪費(fèi)，所以應(yīng)該選擇動態(tài)規(guī)劃解決這個問題。樹上的動規(guī)，是否直接可以寫出下面的狀態(tài)轉(zhuǎn)移方城呢？f[i]:=max(f[son],f[father])+1廢話，顯然是不行的，son和father的值不可能同時得到。但是不要放棄，解決這個沖突的方法，就是采用二次動規(guī)。back第65頁/共74頁第六十五頁，共75頁。網(wǎng)絡(luò)第一次動規(guī)做f[i]:=max(f[son])+1，第二次動規(guī)做f[i]:=max(f[i],f[father]+1)。但是存在一個問題就是如果f[father]的值是從i那里得到的，這樣計算顯然就錯了。不要放棄，在實際操作過程中，f需要記下兩個值，一個是最優(yōu)值，一個是次優(yōu)值，這兩個值必須由不用的子結(jié)點得到。這樣當(dāng)最優(yōu)值發(fā)生矛盾的時候，次優(yōu)值一定不會矛盾。問題就解決了。復(fù)雜度O(N)十分的理想。

back第66頁/共74頁第六十六頁，共75頁?？偨Y(jié)動態(tài)規(guī)劃有很多東西還需要我們更加努力地去探索和學(xué)習(xí).總體上說來,動態(tài)規(guī)劃是個既簡單又不簡單的算法,熟練地掌握了動態(tài)規(guī)劃,也就熟練地控制了比賽.back第67頁/共74頁第六十七頁，共75頁。That’sall!Thankyouforlistening.back第68頁/共74頁第六十八頁，共75頁。動規(guī)練習(xí)題垃圾陷阱（USACO&TJU1087）卡門——農(nóng)夫約翰極其珍視的一條Holsteins奶?！呀?jīng)落了到“垃圾井”中?！袄笔寝r(nóng)夫們?nèi)永牡胤?，它的深度為D(2<=D<=100)英尺?？ㄩT想把垃圾堆起來，等到堆得與井同樣高時，她就能逃出井外了。另外，卡門可以通過吃一些垃圾來維持自己的生命。每個垃圾都可以用來吃或堆放，并且堆放垃圾不用花費(fèi)卡門的時間。假設(shè)卡門預(yù)先知道了每個垃圾扔下的時間t(0<t<=1000)，以及每個垃圾堆放的高度h(1<=h<=25)和吃進(jìn)該垃圾能維持生命的時間f(1<=f<=30)，要求出卡門最早能逃出井外的時間，假設(shè)卡門當(dāng)前體內(nèi)有足夠持續(xù)10小時的能量，如果卡門10小時內(nèi)沒有進(jìn)食，卡門就將餓死。第69頁/共74頁第六十九頁，共75頁。動規(guī)練習(xí)題字符串距離（TJU1086）設(shè)有字符串X，我們稱在X的頭尾及中間插入任意多個空格后構(gòu)成的新字符串為X的擴(kuò)展串，如字符串X為“abcbcd”，則字符串“abcb□cd”，“□a□bcbcd□”和“abcb□cd□”都是X的擴(kuò)展串，這里“□”代表空格字符。如果A1是字符串A的擴(kuò)展串，B1是字符串B的擴(kuò)展串，A1與B1具有相同的長度，那么我們定義字符串A1與B1的距離為相應(yīng)位置上的字符的距離總和，而兩個非空格字符的距離定義為它們的ASCII碼的差的絕對值，而空格字符與其它任意字符之間的距離為已知的定值K，空格字符與空格字符的距離為O。在字符串A、B的所有擴(kuò)展串中，必定存在兩個等長的擴(kuò)展串A1、B1，使得A1與B1之間的距離達(dá)到最小，我們將這一距離定義為字符串A、B的距離。請你寫一個程序，求出字符串A、B的距離。第7