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

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

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

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

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

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

各站按照離Ekaterinburg城的距離編號(hào)。

Ekaterinburg城編號(hào)為1，Sverdlovsk城編號(hào)為N。back第18頁(yè)/共74頁(yè)第十八頁(yè)，共75頁(yè)。買(mǎi)車(chē)票某兩站之間車(chē)票價(jià)格由這兩站的距離X決定.

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

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

當(dāng)L2<X<=L3時(shí)，票價(jià)為C3元.當(dāng)兩站距離大于L3時(shí)沒(méi)有直達(dá)票，所以有時(shí)候要買(mǎi)幾次票做幾次車(chē)才行。比如，在上面的例圖中，2-6沒(méi)有直達(dá)票，有幾種買(mǎi)票方法可以從2-6，其中一種是買(mǎi)C2元的2-3車(chē)票，再買(mǎi)C3元的3-6車(chē)票。back第19頁(yè)/共74頁(yè)第十九頁(yè)，共75頁(yè)。買(mǎi)車(chē)票給定起點(diǎn)站和終點(diǎn)站還有L1,L2,L3,C1,C2,C3，求出要從起點(diǎn)到終點(diǎn)最少要花多少錢(qián).怎么辦確定題目的當(dāng)前狀態(tài)與以前狀態(tài)!back第20頁(yè)/共74頁(yè)第二十頁(yè)，共75頁(yè)。買(mǎi)車(chē)票當(dāng)前狀態(tài)以前狀態(tài)當(dāng)前所在的某個(gè)車(chē)站這一題的以前狀態(tài)其實(shí)只有3種.即滿足3種距離(收費(fèi))情況的3個(gè)車(chē)站.要知道這3個(gè)車(chē)站可以先做一個(gè)預(yù)處理.顯然這3個(gè)車(chē)站在滿足距離限制的條件下應(yīng)該越遠(yuǎn)越好.back第21頁(yè)/共74頁(yè)第二十一頁(yè)，共75頁(yè)。買(mǎi)車(chē)票預(yù)處理很容易想出一個(gè)N^2的預(yù)處理,但是那樣是會(huì)超時(shí)的.由于盡量要讓車(chē)站離得遠(yuǎn)(費(fèi)用是一樣的啊)因此在每種收費(fèi)情況下,每個(gè)車(chē)站的以前狀態(tài)車(chē)站一定是遞增的序列.這里是只要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頁(yè)/共74頁(yè)第二十二頁(yè)，共75頁(yè)。買(mǎi)車(chē)票動(dòng)態(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頁(yè)/共74頁(yè)第二十三頁(yè)，共75頁(yè)。動(dòng)規(guī)的要訣－狀態(tài)有時(shí)候當(dāng)前狀態(tài)確定后,以前狀態(tài)就已經(jīng)確定,則無(wú)需枚舉.back第24頁(yè)/共74頁(yè)第二十四頁(yè)，共75頁(yè)。Tom的煩惱Tom是一個(gè)非常有創(chuàng)業(yè)精神的人，由于大學(xué)學(xué)的是汽車(chē)制造專(zhuān)業(yè)，所以畢業(yè)后他用有限的資金開(kāi)了一家汽車(chē)零件加工廠，專(zhuān)門(mén)為汽車(chē)制造商制造零件。由于資金有限，他只能先購(gòu)買(mǎi)一臺(tái)加工機(jī)器。現(xiàn)在他卻遇到了麻煩，多家汽車(chē)制造商需要他加工一些不同零件（由于廠家和零件不同，所以給的加工費(fèi)也不同），而且不同廠家對(duì)于不同零件的加工時(shí)間要求不同（有些加工時(shí)間要求甚至是沖突的，但開(kāi)始和結(jié)束時(shí)間相同不算沖突）。Tom當(dāng)然希望能把所有的零件都加工完，以得到更多的加工費(fèi)，但當(dāng)一些零件的加工時(shí)間要求有沖突時(shí)，在某個(gè)時(shí)間內(nèi)他只能選擇某種零件加工（因?yàn)樗挥幸慌_(tái)機(jī)器），為了賺得盡量多的加工費(fèi)，Tom不知如何進(jìn)行取舍。第25頁(yè)/共74頁(yè)第二十五頁(yè)，共75頁(yè)。Tom的煩惱Tom的煩惱按結(jié)束時(shí)間排序，枚舉結(jié)束時(shí)間作為當(dāng)前狀態(tài),以前狀態(tài)就是該結(jié)束時(shí)間對(duì)應(yīng)的起始時(shí)間，這是已經(jīng)確定的.back第26頁(yè)/共74頁(yè)第二十六頁(yè)，共75頁(yè)。文字游戲文字游戲(fairfox邀請(qǐng)賽1)

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

單詞是abcdabcd

句子是abcd

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

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

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

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

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

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

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

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

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