動態(tài)規(guī)劃入門-by-mzx

“模擬游戲”——動態(tài)規(guī)劃Bymzx導(dǎo)例一：李震切水題描述Description

jzyz的oi大神李震最近為了讓自己的AC記錄霸占o(jì)j的提交榜，于是點開了oj第十頁usaco銅組專題。寫每道題都需要一定的智商值，然而李震大神開始時擁有無限高的智商。不幸的是：切水題會降智商，而且每切一道水題智商就會降到和這道題要求的智商一樣。 高冷的李震切水題也是有要求的：他只會從第十頁的第一題開始往下切，每切一道題都不會回頭再切比這道題題號小的題。 那么問題來了，第十頁usaco的題也并不全是水題，所以對于以給定方式打開的jzyzoj第十頁，請幫助剛切完一道難度為負的水題的李震計算兩個問題： 1.李震這次切題行動最多能切完多少道題？ 2.切完jzyzoj第十頁需要多少只這樣的李震？我很早就說過要拿這題黑李震的I/O格式輸入格式InputFormat

第一行數(shù)字n表示jzyzoj第十頁一共有n道題(n<=200)

第二行n個數(shù)字，第i個數(shù)字代表題號為i的題目要求的智商值樣例輸入SampleInput

8 38920715530029917015865輸出格式OutputFormat 第一行一個整數(shù)，表示李震最多能切掉的水題數(shù) 第二行一個整數(shù)，表示要切掉所有水題最少要配備的李震只數(shù)樣例輸出SampleOutput

6 2先考慮一下暴力吧

拿到一道題，我們最容易想到的往往是用計算機計算效率來枚舉每一種可能性，這種方法的特點就是最基本、最簡單、最好實現(xiàn)、效率最差。 而對這種搜索方法進行優(yōu)化的方法就是盡可能拋棄那些不可能的可能性或無法達到最優(yōu)值的可能性，這就是所謂的搜索的可行性剪枝和最優(yōu)性剪枝。 然而我今天并不是來講搜索的，但是對搜索進行剪枝的方法具有很強的推廣的可能性。 這道題搜索的枚舉方法很好想，對于每一道水題，李震都有切或者不切的選擇，那么選擇完這n道水題切或不切的狀態(tài)便是一種可能性，時間復(fù)雜度是O(2^n)，對于n為200的數(shù)據(jù)量，你這個程序跑完李震都已經(jīng)把整個oj切完了。如何剪枝？ 現(xiàn)在我們要做的就是對這棵龐大的搜索樹進行剪枝，首先考慮可行性剪枝：記錄一下你上一個選擇的水題的難度，然后碰到一道題之后如果難度比你上一個選擇的水題的難度要高的話你肯定不能選，直接進行下一層。 然而這并沒有什么卵用，最差的情況（整個數(shù)列單調(diào)遞減）時間復(fù)雜度仍然是O(2^n)。 但是對于這樣的搜索模型，最優(yōu)化剪枝幾乎無從下手。 我們要知道的是DFS遞歸只是搜索的一種實現(xiàn)形式而已，我們剪枝的目的就是要求不搜遍每一種組合仍然能夠得到最優(yōu)解。所以我們應(yīng)該考慮另一種枚舉狀態(tài)的方式。另一種枚舉的思路 一個個去枚舉每道題到底來確定一種可能性切不切顯然是不可行的。 換一種思路如何： 在枚舉每道題切不切的時候，李震能不能切這道題取決于他現(xiàn)在的智商，也就是取決于他最近切的一道題的難度，也就是取決于他最近切了哪一道題。似乎是一種方法。 思考一個數(shù)組f[]，f[i]表示選擇切第i道題之后李震最多已經(jīng)切了多少道題，那么我們就 那么，如果我們在確定一種可能性時，通過枚舉哪幾道題切了而不是切了哪幾道題能通過一個簡單的數(shù)組下標(biāo)和一個值來確定這個狀態(tài)的李震現(xiàn)在的智商是多少以及他最多切了多少題。 那么我們只需要考慮這樣一個問題：切第i道題之前最近切了哪一道題就行了，然后再把最近切的那道題在f數(shù)組對應(yīng)的值“傳遞”過來再+1就行了，當(dāng)然，我們需要把李震切完每一道題之后的智商能不能再切這個第i道題考慮上。來看看這種思想的代碼怎么實現(xiàn)。來看看算法

for(inti=1;i<=n;i++){

for(intj=0;j<i;j++)

if(a[j]>=a[i]&&f[j]>f[i])

f[i]=f[j];

f[i]=f[i]+1; }

算法第一行從1開始一次枚舉每一道題所要求的狀態(tài)，即f。當(dāng)然我覺得我這種縮進格式能逼死很多人。 第二行從0開始枚舉切第i道題之前最近切那一道題更好一些。其中f[0]=0,a[0]=﹢∞（你可以用(1<<31)-1）表示李震還沒有切水題時智商是無限大的。 第三行“&&”判斷枚舉到的j難度是否比i高，因為我們要同時保證切了i和j，“&&”后面判斷切j是不是比之前枚舉過的最近切的題更優(yōu)一些。如果兩個條件都滿足，那么在第四行更新。 第五行f[i]++代表從j“傳遞”過來最優(yōu)值之后第i道題是需要切掉的。 第六行是一個萌萌噠花括號，他可是程序很重要的一部分呢（迫真）。我們需要考慮的 設(shè)計一個算法之后我們要考慮三個問題，首先是正確性，其次是效率，然后是程序怎么去實現(xiàn)。當(dāng)然這里我指的是100分的算法，騙分和暴力也都能拿到分數(shù)的，一個算法的實現(xiàn)也有很多方法。 正確性問題在我們看來是一個很簡單的問題，這是那些需要我們給他們講數(shù)學(xué)必修三的菜鳥才需要考慮的問題，然而有些時候?qū)τ谒惴ㄕ_性的嚴謹證明是十分有必要的，特別是這種高級的算法。 然后是效率，這才是我們最關(guān)心的問題，如果你連兩個for循環(huán)的時間復(fù)雜度都不會算的話就轉(zhuǎn)文吧。很顯然是O(n^2)，甚至更嚴謹一點我們可以說是Θ(n^2)。 動態(tài)規(guī)劃的程序?qū)崿F(xiàn)是非常非常非常非常（因為很重要所以說四遍）簡單的，甚至比搜索還親民。但是這并不意味著你對于下標(biāo)的枚舉能很放松，一些很嚴謹?shù)念}目有時候你區(qū)間少個端點就會全盤皆輸。然而動態(tài)規(guī)劃的程序?qū)崿F(xiàn)還有另一個可講的地方，那就是實現(xiàn)的大致思路有兩個：遞推和記憶化搜索。前者用循環(huán)枚舉每一層實現(xiàn)，后者用遞歸調(diào)用函數(shù)實現(xiàn)；前者的優(yōu)勢是高效，而后者較容易理解，但是關(guān)于哪個實現(xiàn)起來更簡單，這要取決于題目的類別，一般的線性動規(guī)用循環(huán)遞推會更親民一些，區(qū)間dp兩個都差不多，而樹規(guī)和狀壓dp如果用遞推寫簡直就是rlgl。前一頁的程序使用的是前者。我們?yōu)楹我@樣做 關(guān)于這個算法，我需要講的就是正確性和效率，并從這兩個方面來剖析一下動態(tài)規(guī)劃的基本思想： 正確性：首先我們考慮的僅僅是第i道題如果切了，這時候李震最多切了多少道題，所以這個正確性是很容易證明的，每一道題都從之前切過的題中尋找一個可能的最優(yōu)值，然后“繼承”過來，到最后我們需要做的僅僅就是遍歷f數(shù)組尋找最大值。在這里我不想給出十分嚴謹?shù)淖C明過程，因為我覺得那并沒有什么太大的意義。 效率：我們使用的并不是非確定機，所以這道題再高效也不可能達到O(n)水平，我們用的這種算法仍然需要去枚舉每一種狀態(tài)，以及這種狀態(tài)是從前面的哪一種狀態(tài)“轉(zhuǎn)移”過來的，但是我們通過改變了一下思路就把一個指數(shù)級的算法變成了一個多項式級的算法，動態(tài)規(guī)劃到底神奇在哪里了呢？如何理解動態(tài)規(guī)劃 首先看一看f數(shù)組，他是一維的，數(shù)組中的每一個元素都代表了一種可能性，所以一共有n種可能性，但在這之前的暴力搜索卻有足足2^n種可能性，為什么僅僅限制了“必須拿這道題”就把可能性縮小了這么多？ 上面這么說其實是不嚴謹?shù)?，因為我們在遍歷f數(shù)組的時候并不知道數(shù)組中的每一個元素代表的是一個什么樣的可能性，也就是我們知道f[i]表示如果一定切第i個題最多切了多少了題，并不知道切的是哪幾道題，也就是說，我們記錄的是最優(yōu)值，而不是狀態(tài)。然后我們?nèi)绾未_定f[i]的最優(yōu)值是“合法”的呢？那就是它的前驅(qū)對應(yīng)的題的難度一定比他高。 現(xiàn)在我們來考慮一下：為什么我們僅從切第i道題之前最近切的一道題就能確定它一定“合法”呢？切到i時的狀態(tài)可是有2^(i-1)種的。但我們只需要去枚舉i-1個它之前最近切的一道題就可以，為什么？因為切i的前驅(qū)j之前究竟切了哪幾道題，并不影響能不能切到i，所以我們在考慮f[i]時只需要考慮在它之前切哪一道題是最優(yōu)的(f[j]>f[i])而且是合法的(a[j]>=a[i])，而不需要考慮在j之前究竟切了哪幾道，因為這并無卵用。動態(tài)規(guī)劃的基本原理

從這道例題我們能看出來我們只需要一個f數(shù)組就可以完成對所有可能最優(yōu)狀態(tài)的枚舉，也就是完成了最優(yōu)化剪枝，那么在考慮一個f[i]時，我們僅僅從下標(biāo)i和f[i]的數(shù)值就能看出來這表示的是一個什么樣的狀態(tài)，以及在這個狀態(tài)下的最優(yōu)值，而從f[j]到f[i](j<i)，就是實現(xiàn)了從之前的幾個狀態(tài)到現(xiàn)在這種狀態(tài)的“繼承”，就是我們俗稱的狀態(tài)轉(zhuǎn)移。 動態(tài)規(guī)劃的一個很明顯的特征就是下標(biāo)表示狀態(tài)，那么為什么我們只需要一個或幾個數(shù)字就可以表示狀態(tài)呢？為什么一個i就可以而不是用一個bool數(shù)組來表示究竟選了哪幾道題呢？因為我們考慮的是最優(yōu)解，而i之前選了那幾題跟選了i之后能夠選擇哪道題并沒有半毛錢的關(guān)系，這就是我們說的無后效性；而i最優(yōu)能夠保證后面從i轉(zhuǎn)移過去的狀態(tài)一定是最優(yōu)的，這就是我們所謂的最優(yōu)化原理。 我們可以發(fā)現(xiàn)一個f[i]在之后的狀態(tài)轉(zhuǎn)移中可能被“用到”很多次，但我們并不用多次去求解這個問題，只需要求過一次并保存下來就行了，一個子問題(f[i])的最優(yōu)解依賴于它的子問題(f[j])的最優(yōu)解，并且這些最優(yōu)解并不需要反復(fù)被求解，就是最優(yōu)子jié構(gòu)。為什么將動態(tài)規(guī)劃稱為“模擬游戲” 讓我們來看看樣例(n=8)：38920715530029917015865 如果我們跑完一遍程序，那么整個運行時的效果是什么樣的呢？ 我覺得這張圖片已經(jīng)能夠很形象地表現(xiàn)出動態(tài)規(guī)劃的具體思想了：最優(yōu)子結(jié)構(gòu)、無后效性和在我觀念中的它的模擬思想。 動態(tài)規(guī)劃的基本思想就是用一個或幾個下標(biāo)表示狀態(tài)，然后這幾個下標(biāo)對應(yīng)的數(shù)組中的數(shù)值就是在這個狀態(tài)下的最優(yōu)值。通過去尋找并記錄每個狀態(tài)的最優(yōu)值，并在之后的計算中用到這些狀態(tài)（即子問題）的最優(yōu)值，就能夠把指數(shù)級別的搜索算法變成多項式級別的動態(tài)規(guī)劃算法。 在進行狀態(tài)轉(zhuǎn)移時，我們只關(guān)心前一個狀態(tài)的合法性和最優(yōu)性，而不關(guān)注它之前的狀態(tài)，所以我們就可以把每一個狀態(tài)的下標(biāo)對應(yīng)的狀態(tài)想象成“具體的”，而把這個狀態(tài)的“前驅(qū)狀態(tài)”看為“模糊的”，意思是我們不管一個值的過去，我們只看重現(xiàn)在他對我們有什么價值。重構(gòu)最優(yōu)解

對于這道題的第二問，也就是需要多少只這樣的李震才能切完oj第十頁，不屬于動態(tài)規(guī)劃的范疇內(nèi)，是一個貪心的算法，所以在這里不再討論。 那么我們來考慮一個新的問題：李震在切題切得最多的情況下，切的是哪幾道題？ 我們在進行dp的時候，只知道每一個狀態(tài)的最優(yōu)值是從哪一個狀態(tài)繼承過來的，而不知道它的前一個狀態(tài)之前是什么樣的，這是不是就代表我們無法從我們已知的最優(yōu)解“還原”出最優(yōu)解具體的狀態(tài)呢？不，我們在計算出一個狀態(tài)最優(yōu)解的時候，可以記錄一下這個狀態(tài)是從哪一個狀態(tài)轉(zhuǎn)移過來的，然后它的前驅(qū)狀態(tài)也會知道它的前驅(qū)的前驅(qū)是哪一個，就像你可能不知道自己的太爺爺是誰，但你爺爺知道他的爺爺是誰，用這種思想進行遞歸輸出最優(yōu)解即可，所以我們只需要再加一位數(shù)組記錄每個i對應(yīng)的最優(yōu)值的前驅(qū)，這個前驅(qū)記錄的就是f[i]最優(yōu)值對應(yīng)的那個j值。具體代碼這里不再給出，因為我覺得這個比較重要，自己試著寫一下可能更好。 有些動態(tài)規(guī)劃問題在讓你計算最優(yōu)解的同時會讓你指出該如何組成這樣的最優(yōu)解，畢竟這是一個很現(xiàn)實的問題。所以在剛開始學(xué)的時候最好建立起如何重構(gòu)最優(yōu)解的概念，這不僅能幫你多AC掉幾道題，同時還能幫你更加深入地理解動態(tài)規(guī)劃的“層次性”，也就是最優(yōu)子結(jié)構(gòu)和無后效性的概念。小結(jié) 這個課件的題目叫《“模擬游戲”——動態(tài)規(guī)劃》，但在這里我并沒有過多地提到“模擬”，但在以后的例題講解中我會經(jīng)常通過圖片來講述動態(tài)規(guī)劃的“模擬過程”，也就是狀態(tài)轉(zhuǎn)移。我們可以通過在腦中想象一組下標(biāo)對應(yīng)了一個什么樣的狀態(tài)，以及所有的這些狀態(tài)是如何實現(xiàn)相互遞推轉(zhuǎn)移，讓自己能夠更加具象地理解一道題目。每道題目都有自己的一組組狀態(tài)，每個狀態(tài)對應(yīng)的最優(yōu)值不重要，重要的是這些狀態(tài)的靜態(tài)（即它表示什么）和動態(tài)（即它們之間如何實現(xiàn)轉(zhuǎn)移）的形態(tài)在我們的腦?；蛘呒垙埢蛘弋媹D軟