算法設(shè)計與分析 課件 第六章 動態(tài)規(guī)劃

動態(tài)規(guī)劃第六章主講人：邱維陽E-mail:qwynick@163.com動態(tài)規(guī)劃的思想核心概念：狀態(tài)記錄：合理記錄、表示問題狀態(tài)轉(zhuǎn)移：將子問題的解合并為原問題的解前提條件：最優(yōu)子結(jié)構(gòu)：原問題的最優(yōu)解可由某個（些）子問題的最優(yōu)解轉(zhuǎn)移而來無后效性：將子問題的解轉(zhuǎn)移到原問題時，不用關(guān)心子問題最優(yōu)解的起源重疊子問題：反復(fù)利用子問題的解，減少計算量上述概念比較抽象，可以結(jié)合各種例題進(jìn)行體會和理解。線性動態(tài)規(guī)劃6.2線性動態(tài)規(guī)劃——動態(tài)規(guī)劃入門線性動態(tài)規(guī)劃主要特征：狀態(tài)可以表示為某種序列：比如一維線性序列或者二維、三維陣列數(shù)據(jù)表示。狀態(tài)的轉(zhuǎn)移表現(xiàn)為：由某個位置的數(shù)據(jù)（狀態(tài)）按照某種固定的順序計算另一個位置的數(shù)據(jù)（狀態(tài)）。線性動態(tài)規(guī)劃例6-1：升國旗的平臺一共需要上N級臺階，你每一步可以上一級或者兩級，問一共有多少種登上平臺的走法？可嘗試枚舉n=1、2、3……時的走法，并找一下規(guī)律。很容易發(fā)現(xiàn)當(dāng)n=1、2、3、4、5……時的走法有1、2、3、5、8種。即斐波那契數(shù)列。但是這是為什么呢？線性動態(tài)規(guī)劃分析：假定你已經(jīng)走到了第n級臺階，很顯然你的前一步只可能站在第n-2或者n-1級臺階。也就是，如果你能走到n-2或者n-1級臺階，那么你都可以通過再走一步到達(dá)第n級臺階。所以如果你走到第n-2級臺階有x種方式，走到第n-1級臺階有y種方式，則走到第n級臺階就有x+y種方式。我們記走到第i級臺階的方案數(shù)為dp[i]（狀態(tài)記錄），則可以得到下面的關(guān)系：dp[i]=dp[i-2]+dp[i-1]這個遞推關(guān)系正好與斐波那契數(shù)列一致。線性動態(tài)規(guī)劃例6-1小結(jié)：作為引子，本例非常簡單，但是卻已經(jīng)蘊(yùn)含了動態(tài)規(guī)劃的思想，從1走到n的問題的解，由1走到n-2的解和1走到n-1的解合并而成，且走得近的問題構(gòu)成了重疊子問題。復(fù)雜度為??(??)。線性動態(tài)規(guī)劃例6-2：給你一個長度為??的整數(shù)序列??，請你找出一段連續(xù)子序列，使得該段子序列的和最大。比如??=[6,?1,5,4,?7]，則最大的子序列為6-1+5+4=14。直接暴力枚舉區(qū)間起點和終點，復(fù)雜度將是??(??2)。線性動態(tài)規(guī)劃分析：觀察一下，有時候我們需要包含負(fù)數(shù)以獲得后面更大的正數(shù)序列（如示例）；但有時候，又不需要包含負(fù)數(shù)，比如??=[6,?10,5,?7]。那么如何找到一個統(tǒng)一的做法呢？或者說是否會包含負(fù)數(shù)的判定依據(jù)是什么呢？線性動態(tài)規(guī)劃分析：仔細(xì)對比??=[6,?1,5,4,?7]和??=[6,?10,5,?7]，可以發(fā)現(xiàn)，對于前者，6-1=5，即是說包含負(fù)數(shù)之后總和依然為正，會對后面的區(qū)間形成正的貢獻(xiàn)；而后者則不然。所以我們可以得出一個規(guī)律，如果包含負(fù)數(shù)之后仍然為正，就繼續(xù)向后延伸（有正貢獻(xiàn)），反之則不要延伸（由負(fù)貢獻(xiàn)）。如果我們用dp[i]表示到i位置為止的最大子段和，則可以得出下面的轉(zhuǎn)移方程：dp[i]=max(dp[i-1],0)+d[i]線性動態(tài)規(guī)劃例6-2小結(jié)：只需要將??數(shù)組循環(huán)一遍即可得到以每個數(shù)作為區(qū)間右端點的最大區(qū)間和，復(fù)雜度為??(??)。這是一個非常經(jīng)典的動態(tài)規(guī)劃入門題，但是仍然值得用來品味動態(tài)規(guī)劃的前提條件。在本例中，以i為區(qū)間右端點的最大區(qū)間和由以i-1為區(qū)間右端點的最優(yōu)區(qū)間加上i自己和或者由i自己單獨作為一個區(qū)間兩者中更優(yōu)的一個轉(zhuǎn)移而來。這里很好地體現(xiàn)了最優(yōu)子結(jié)構(gòu)和無后效性，請同學(xué)們注意體會。線性動態(tài)規(guī)劃例6-3：第i個木樁的高度為hi，運(yùn)動員一開始在編號為1的木樁上，每次可以跳到所在木樁后面第1個或第2個木樁上。當(dāng)運(yùn)動員從第i個木樁跳到第j個木樁時，他將消耗體力|hi-hj|。試問，跳到第n個木樁，最少需要消耗多少體力？直接暴力枚舉所有的跳躍方案，復(fù)雜度將是O(2n)。線性動態(tài)規(guī)劃分析：思考：如果我們到達(dá)終點n所耗費的體力是dp[n]，那么，這個dp[n]是怎么來的？按照題目的限制，只能是由n-2或者n-1位置跳過來。所以？線性動態(tài)規(guī)劃分析：如果由n-2跳過來，則：dp[n]=dp[n-2]+|hn-hn-2|同理，如果由n-1位置跳過來，則：dp[n]=dp[n-1]+|hn-hn-1|很顯然，我們會選擇一個總體力開銷更小的方案，即dp[n]=min(dp[n-2]+|hn-hn-2|,dp[n-1]+|hn-hn-1|)線性動態(tài)規(guī)劃分析：我們分析了對于終點的轉(zhuǎn)移策略，很顯然，這樣的轉(zhuǎn)移策略對前面的各個位置也都適用。同時，要使到達(dá)終點的開銷盡量小，必然希望到達(dá)前面各個點的開銷（子問題）也盡量小。所以這滿足最優(yōu)子結(jié)構(gòu)的條件。因此我們可以從前往后逐步計算出到達(dá)各個位置的最小開銷。dp[i]=min(dp[i-2],dp[i-1])線性動態(tài)規(guī)劃例6-3小結(jié)：很顯然，只需要將??數(shù)組循環(huán)一遍即可得到以每個數(shù)作為區(qū)間右端點的最大區(qū)間和，復(fù)雜度為??(??)。在本例中，跳到i位置的最小開銷一定由其前面兩個位置之一轉(zhuǎn)移而來，同時，要使得跳到i的開銷盡量小，也要讓跳到i-2和i-1的開銷盡量小，即從最優(yōu)子結(jié)構(gòu)轉(zhuǎn)移而來。此外，在考慮跳到第i個點的開銷時，單純考慮了跳到i-2和i-1級的總開銷以及從他們跳到第i級這一步的開銷，并未關(guān)注之前是如何跳到i-2和i-1的，此即無后效性。重疊子問題怎么體現(xiàn)？線性動態(tài)規(guī)劃例6-4：暑假共有n天，每天可以選擇學(xué)習(xí)一門課，在第i天時如果學(xué)習(xí)三門課A、B、C可獲得的知識量分別為ai、bi、ci，為了避免厭倦，憨憨不會在連續(xù)兩天學(xué)習(xí)同一門專業(yè)課。整個假期憨憨能獲得的最大知識量是多少？直接暴力枚舉所有的學(xué)習(xí)方案，復(fù)雜度將是O(2n)。線性動態(tài)規(guī)劃分析：參照例6-3的分析，這個問題應(yīng)該如何分析？很顯然，如果如果第i天選擇了A課程，則第i+1天可選擇的課程為BC，如果第i天選擇的是B課程，則第i+1天可選擇的課程為AC……同時，類比前一個例題，可以發(fā)現(xiàn)如果我們在第i天選擇某門課程X，后續(xù)的課程選擇并不受第i天之前選擇的影響。所以？線性動態(tài)規(guī)劃分析：由于第i天的選擇會對后續(xù)的轉(zhuǎn)移產(chǎn)生不同的影響，我們需要分別記錄在第i天的不同選擇情況下的最優(yōu)解：即可以用dpa[i]、dpb[i]、dpc[i]分別表示在第i天選擇A、B、C課程的最大收益。根據(jù)題目要求，我們在第i天選擇A課程的前提是前一天選擇了B或者C，即：dpa[i]=max(dpb[i-1],dpc[i-1])+a[i]學(xué)習(xí)B、C課程的轉(zhuǎn)移方程也可類似得出。不斷向后計算，直到第n天即可得到全局最優(yōu)解。線性動態(tài)規(guī)劃例6-4小結(jié)：很顯然，只需要將天數(shù)遍歷一遍即可得到每一天學(xué)習(xí)A、B、C課程的最優(yōu)解，復(fù)雜度為??(??)。最優(yōu)子結(jié)構(gòu)如何體現(xiàn)？無后效性如何體現(xiàn)？。重疊子問題如何體現(xiàn)？線性動態(tài)規(guī)劃例6-5：數(shù)字三角形的第i行有i個數(shù)字，分別表示各處的文物價值，考古人員由第一行那個唯一數(shù)字的位置進(jìn)入陵墓，并可以向下一行中與當(dāng)前數(shù)字位置最接近的兩個數(shù)字之一的位置前進(jìn)。求能收集的文物的最大價值。直接暴力枚舉所有的行進(jìn)方案，復(fù)雜度將是O(2n-1)。線性動態(tài)規(guī)劃分析：參照例6-3、6-4的分析，這個問題應(yīng)該如何分析？很顯然，從示例里面可以看到，貪心=7+6+2+7+6=28，不成立。隱約仍然有無后效性、最優(yōu)子結(jié)構(gòu)等性質(zhì)？所以？線性動態(tài)規(guī)劃分析：由于除邊界位置外，其余位置只可能由其上一行的兩個位置轉(zhuǎn)移而來，為了使總和更大，很顯然，應(yīng)當(dāng)選擇由更大的一個轉(zhuǎn)移而來，如果我們用dp[i][j]表示走到第i行第j列的總和的最大值，用d[i][j]表示第i行第j列的文物價值，則有：dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+d[i][j]線性動態(tài)規(guī)劃例6-5小結(jié)：很顯然，只需要從上到下將各行遍歷一遍即可得到最優(yōu)解，復(fù)雜度為??(??2)。最優(yōu)子結(jié)構(gòu)如何體現(xiàn)？無后效性如何體現(xiàn)？重疊子問題如何體現(xiàn)？線性動態(tài)規(guī)劃例6-6：給定一個數(shù)列，請將其中若干個數(shù)字移走，使得剩下的數(shù)字呈現(xiàn)遞增的關(guān)系。剩余數(shù)字構(gòu)成的遞增序列的長度最長可以為多少？直接暴力枚舉所有的移除方案，復(fù)雜度將是O(2n)。線性動態(tài)規(guī)劃分析：本問題又該如何分析？如果我們從最后一位的數(shù)字4開始向前搜索，第一個能與4構(gòu)成上升序列的是第5位的1，再往前就沒了；第二個能與4構(gòu)成上升序列關(guān)系的是第3位的2，然后是第2位的2，他們又同時能與第1位的1構(gòu)成上升序列關(guān)系。1

2

2519944122111搜索過程分析：本問題又該如何分析？同理，我們考察倒數(shù)第二位的數(shù)字9，他會找到5，5又會找到2，2又會找到1……。之后，倒數(shù)第三位的9又會重復(fù)此計算過程……線性動態(tài)規(guī)劃1

2

2

5

19949122111搜索過程52211線性動態(tài)規(guī)劃分析：但是觀察搜索過程可以發(fā)現(xiàn)，對于黃色和藍(lán)色的2來說，無論是4與他們連接還是5與他們連接，或者是9與他們連接，再往前都只能再連一個1。同樣，兩個9連接上5之后，再往前能連接的情況也都是一樣的。因為再往前能連接的數(shù)僅被5所限（無后效性），即繼續(xù)往前能組成的長度是固定的，因而我們其實沒有必要采用搜索來窮舉所有方案。4122111912211152211線性動態(tài)規(guī)劃分析：通過前面的分析，我們發(fā)現(xiàn)，以第i個數(shù)字為終點的上升子序列長度是由d[i]的數(shù)值大小與他前面的序列所確定的，且對于i’>i，如有d[i’]>d[i]，則第i’個數(shù)就能接上以第i個數(shù)作為終點的上升子序列，構(gòu)成一個更長的上升子序列。如果我們用dp[i]表示以第i個數(shù)字為終點的最長上升子序列長度，則有：dp[i]=max(dp[j])+1(滿足1≤j<i，且d[j]<d[i])線性動態(tài)規(guī)劃例6-6小結(jié)：很顯然，一共需要求n個數(shù)的最長上升子序列，求第i個最長上升子序列時需要遍歷其前面i-1個數(shù)，復(fù)雜度為??(??2)。最優(yōu)子結(jié)構(gòu)如何體現(xiàn)？無后效性如何體現(xiàn)？重疊子問題如何體現(xiàn)？還有復(fù)雜度更低的做法嗎？線性動態(tài)規(guī)劃例6-7：給定兩個數(shù)列長度分別為n和m，請將其中若干個數(shù)字移走，使得兩個數(shù)列剩余的部分一致。剩余數(shù)列的最長長度是多少？直接暴力枚舉所有的移除方案，復(fù)雜度將是O(2n+m)。線性動態(tài)規(guī)劃分析：類比例6-6，本問題又該如何分析？我們定義完整的問題為，從第一個串的n個字符中刪除部分，從第二個串的m個字符中刪除部分，讓剩余部分相同，且盡量長。按照之前的經(jīng)驗，我們可以將子問題（狀態(tài)）描述為：從第一個串的前i個字符中刪除部分，從第二個串的前j個字符中刪除部分，讓剩余部分相同，且盡量長。我們記該問題的最優(yōu)解為dp[i][j]。分析：狀態(tài)如何轉(zhuǎn)移？很顯然，如果第一個串的第i位與第二個串的第j位相等，我們直接保留兩者，即：dp[i][j]=dp[i-1][j-1]+1如果兩者不等，又該如何？我們可以考慮舍棄一個，具體舍棄哪個呢？顯然是舍棄后，剩余部分匹配長度盡量長的一個方案，即：dp[i][j]=max(dp[i-1][j],dp[i][j-1])線性動態(tài)規(guī)劃線性動態(tài)規(guī)劃例6-7小結(jié)：很顯然，我們只需要將兩個串逐位進(jìn)行比較即可。復(fù)雜度為??(nm)。最優(yōu)子結(jié)構(gòu)如何體現(xiàn)？無后效性如何體現(xiàn)？重疊子問題如何體現(xiàn)？線性動態(tài)規(guī)劃總結(jié)注意體會、學(xué)會如何表示狀態(tài)、如何轉(zhuǎn)移狀態(tài)。注意以下特征：無后效性、最優(yōu)子結(jié)構(gòu)、重疊子問題。多練習(xí)多思考多體會。背包問題6.3背包問題——一類非常經(jīng)典的動態(tài)規(guī)劃問題背包問題例6-9：0-1背包。有n個物品，第i個物品的價值為vi，重量wi。給定一個載重量為m的背包用于裝物品。在不超過背包載重量的前提下，如何選擇物品使得背包中物品的總價值最大？所有參數(shù)不超過1000。直接暴力枚舉所有的移除方案，復(fù)雜度將是O(2n)。背包問題分析：優(yōu)先拿單位重量價值高的？考慮m=5，w1=2,

w2=4，v1=5,

v2=8。此時顯然物品1的單位價值更大，但是我們卻應(yīng)該拿物品2。分析：如果我們直接枚舉所有的物品要或者不要，那么復(fù)雜度又是指數(shù)級的。聯(lián)想我們在前一節(jié)也遇到了大量的指數(shù)級問題，通過動態(tài)規(guī)劃降為了多項式級的復(fù)雜度。其原理即利用最優(yōu)子結(jié)構(gòu)和重疊子問題的性質(zhì)，避免了大量無效的狀態(tài)枚舉。那么本問題？背包問題背包問題分析：有的物品本身是不夠優(yōu)秀的，或者他與其他物品的組合的結(jié)果不夠優(yōu)秀，所以我們在進(jìn)行價值計算的時候不需要在這些不優(yōu)的組合的基礎(chǔ)上進(jìn)行進(jìn)一步計算。對于每個重量，我們只需要在該重量的最大價值方案基礎(chǔ)上進(jìn)一步計算即可。背包問題分析：我們可以用dp[i][j]表示在考察過前i個物品后，重量為j的方案的最大價值。當(dāng)我們考察第i個物品時，對于每個重量j，我們計算出對應(yīng)的dp[i][j]值即可：dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])這里，max中的第一項表示我們舍棄第i號物品，用前i–1個物品組成重量為j的組合；第二項表示我們使用第i號物品，此時我們只能用前i–1號物品組成重量為j–w[i]的組合，總價值在此基礎(chǔ)上需要加上第i號物品的價值。背包問題分析：我們可以用dp[i][j]表示在考察過前i個物品后，重量為j的方案的最大價值。右圖是背包載重量為5，三個產(chǎn)品的重量分別為3、2、4，價值分別為2、5、8的運(yùn)行效果?？梢钥吹皆诳紤]過第1個物品后，載重量為3、4、5可獲得價值2；在考慮過物品2后，重量為2、3、4時可以獲得價值5，重量為5時可獲得價值7。三輪完成后，載重量為5時，可以獲得的價值為8。背包問題分析：在實際操作中，對于01背包問題一般并不會用n×m的數(shù)組保存數(shù)據(jù)。從上面的示意圖可以看出，當(dāng)i=2的時候，i=1的數(shù)據(jù)其實已經(jīng)無用了；當(dāng)i=3的時候，i=1的數(shù)據(jù)已經(jīng)沒用了。我們可以采用滾動數(shù)組的形式節(jié)省空間。當(dāng)然，更直接的方法是在一維數(shù)組上進(jìn)行原地修改。（后面介紹）背包問題例6-9小結(jié)：每個物品都需要將所有的m個不同重量都更新一遍，一共n個物品，復(fù)雜度O(nm)。最優(yōu)子結(jié)構(gòu)如何體現(xiàn)？無后效性如何體現(xiàn)？重疊子問題如何體現(xiàn)？背包問題例6-10：完全背包。有n類物品，第n類物品每個價值vi，重量wi，每類物品的個數(shù)不限。給定一個載重量為m的背包，求問如何選擇物品，在不超過背包載重量的前提下，使得背包中物品的總價值最大。（本題所有輸入?yún)?shù)不超過1000）與例6-9有什么區(qū)別？背包問題分析：在01背包問題中，每個物品只能用一次，因此dp[i][j]是由dp[i-1][j-w[i]]+v[i]轉(zhuǎn)移而來。在本例中，每個物品都可以無限使用，所以dp[i][j]不僅可以由dp[i-1][j-w[j]]轉(zhuǎn)移而來，還可以由dp[i][j-w[j]]轉(zhuǎn)移而來，即可以由已經(jīng)使用過第i號物品的組合方案再繼續(xù)加入i號物品，即：dp[i][j]=max(dp[i-1][j],max(dp[i-1][j-w[i]],dp[i][j-w[i]])+v[i])背包問題分析：dp[i][j]=max(dp[i-1][j],max(dp[i-1][j-w[i]],dp[i][j-w[i]])+v[i])這里第一個max的第一項表示不放入第i號物品；第二個max的第一項表示用了一個第i號物品形成重量j；第二個max的第二項表示再已經(jīng)用過物品i的基礎(chǔ)上繼續(xù)使用物品i，即由本輪的dp[i]繼續(xù)進(jìn)行轉(zhuǎn)移。背包問題分析：我們可以用dp[i][j]表示在考察過前i個物品后，重量為j的方案的最大價值。右圖是背包載重量為5，三個產(chǎn)品的重量分別為3、2、3，價值分別為5、4、8的運(yùn)行效果。0000001234500055500458900488120i=0i=1i=2i=3背包問題例6-10小結(jié)：每個物品都需要將所有的m個不同重量都更新一遍，一共n個物品，復(fù)雜度O(nm)。最優(yōu)子結(jié)構(gòu)如何體現(xiàn)？無后效性如何體現(xiàn)？重疊子問題如何體現(xiàn)？背包問題01背包和完全背包小結(jié)：01背包和完全背包作為經(jīng)典的背包問題，狀態(tài)較為簡單，在實際操作過程中，往往僅采用一維數(shù)組進(jìn)行計算。即，用dp[j]記錄重量為j時的最大價值，在解決01背包問題時，我們可以將j從m更新到w[i]，這樣先更新大的重量，再更新小的重量，可以避免同一個物品被多次使用。相應(yīng)地，再解決完全背包問題時，我們可以將j從w[i]更新到m，這樣先更新小的重量，再更新大的重量，可以讓同一個物品被多次使用。背包問題例6-11：多重背包問題。有n類物品，單個第i類物品的價值為wi，重量vi，每類物品的個數(shù)為ci。給定一個載重量為m的背包。求問如何選擇物品，在不超過背包載重量的前提下，使得背包總價值最大（本題所有輸入?yún)?shù)不超過100）。比如，背包載重量為10，有兩種物品重量分別為1和3，價值分別為1和2，數(shù)量分別為8和2，經(jīng)過分析和試算可以得出應(yīng)該取走7個第一類物品和1個第二類物品?？傆嬋〉脙r值為9。更復(fù)雜了？背包問題分析：對于多重背包問題，最簡單的處理方式就是將ci個第i號物品處理成ci個獨立的重量為wi，價值為vi的物品即可?？傮w來看，就是∑ci個物品組成的01背包問題。背包問題例6-11小結(jié)：每個物品都需要將所有的m個不同重量都更新一遍，一共∑ci個物品，復(fù)雜度O(nmc)。但是此問題其實通過更高級的處理技術(shù)，可以將復(fù)雜度降低到O(nmlogc)，甚至O(nm)。有興趣的同學(xué)可以自行查閱資料。背包問題例6-12：二維背包。有n個物品，第i個物品的體積為si，價值為vi，重量wi。給定一個容積為m、載重量為r的背包。求問如何選擇物品，在不超過背包容積和載重量的前提下，使得背包總價值最大。（本題所有輸入?yún)?shù)不超過100）更復(fù)雜了？背包問題分析：相對于之前的問題，本問題將約束條件擴(kuò)展到了兩個，如何求解？應(yīng)該可以想到，我們只需要記錄在體積為j，重量為k時的最大價值即可?？梢杂胐p[j][k]來表示前述狀態(tài)，如果加入物品i后達(dá)到該狀態(tài)，則加入該物品前的狀態(tài)即為：dp[j-s[i]][k-w[i]]背包問題分析：參照0-1背包的轉(zhuǎn)移方式，在考察第i號物品時，需要同時考慮體積和重量的影響：dp[j][k]=max(dp[j][k],dp[j-s[i]][k-w[i]]+v[i])這里max的第一項表示不加入第i號物品，即最大價值保持不變；而第二項表示加入第i號物品，此時其余物品的總體積為j-s[i]，總重量為k-w[i]，對應(yīng)的價值即為dp[j-s[i]][k-w[i]]。背包問題例6-12小結(jié)：每個物品都需要將所有的m個不同容積和r個不同重量的價值都更新一遍，一共n個物品，復(fù)雜度O(nmr)。最優(yōu)子結(jié)構(gòu)如何體現(xiàn)？無后效性如何體現(xiàn)？重疊子問題如何體現(xiàn)？背包問題總結(jié)背包模型：非常重要的模型，多種衍生問題。注意不同背包問題的狀態(tài)記錄。注意不同背包問題的狀態(tài)轉(zhuǎn)移順序。背包問題有非常多的衍生內(nèi)容，打好基礎(chǔ)非常重要。記憶化搜索與區(qū)間動態(tài)規(guī)劃6.4記憶化搜索與區(qū)間動態(tài)規(guī)劃

——換一個方向進(jìn)行動態(tài)規(guī)劃記憶化搜索與區(qū)間動態(tài)規(guī)劃例6-14：已知斐波那契數(shù)列f(1)=f(2)=1，其他f(x)=f(x-2)+f(x-1)，輸入正整數(shù)n，輸出f(n)，n不超過46。

這個題目很簡單，直接for循環(huán)遞推求解即可。記憶化搜索與區(qū)間動態(tài)規(guī)劃分析：同學(xué)們應(yīng)該也知道，也可以采用遞歸的方式計算斐波那契數(shù)列即，要求解f(n)如果n<=2：返回1；否則：返回前兩項之和f(n-2)+f(n-1)。這樣做有什么問題？記憶化搜索與區(qū)間動態(tài)規(guī)劃分析我們可以畫出遞歸求解的遞歸樹。從右側(cè)的樹中可以觀察到兩個特點，①所有的遞歸終點都是n=1或者n=2，其值為1。由于斐波那契數(shù)列的結(jié)果：指數(shù)級上升由特征①：遞歸的結(jié)點數(shù)指數(shù)級上升。速度極慢。f(5)f(3)f(4)f(1)f(2)f(2)f(3)f(1)f(2)f(4)f(2)f(3)f(1)f(2)f(6)記憶化搜索與區(qū)間動態(tài)規(guī)劃分析②同一個數(shù)字，無論出現(xiàn)在何處，其子樹的形態(tài)都一致。由特征②：同樣數(shù)值的節(jié)點沒必要反復(fù)計算?？梢栽谑状斡嬎阃瓿珊蟆涗浗Y(jié)果——后續(xù)直接調(diào)用。dp[i]=dp[i-2]+dp[i-1]以上dp數(shù)組的數(shù)值僅在第一次訪問i節(jié)點時進(jìn)行計算。遞歸終點：n=1、2。f(5)f(3)f(4)f(1)f(2)f(2)f(3)f(1)f(2)f(4)f(2)f(3)f(1)f(2)f(6)記憶化搜索與區(qū)間動態(tài)規(guī)劃例6-14小結(jié)：由于原問題可能多次拆分出同樣的子問題，而子問題的結(jié)果是確定的，因此只需要在第一次拆分出該子問題時進(jìn)行計算并保存結(jié)果。復(fù)雜度O(n)。最優(yōu)子結(jié)構(gòu)如何體現(xiàn)？無后效性如何體現(xiàn)？重疊子問題如何體現(xiàn)？記憶化搜索與區(qū)間動態(tài)規(guī)劃例6-15：給定一個n×m的矩形滑雪場，已知各處的海拔，滑雪者只能由高處滑向低處，請求出一個最長的滑雪路徑。某滑雪場的海拔分布如圖所示。

在這樣一個海拔分布的滑雪場，可以選擇從中間的25出發(fā)，逆時針轉(zhuǎn)圈滑行，滑出一個長度為25的路徑。記憶化搜索與區(qū)間動態(tài)規(guī)劃分析：很顯然，暴力搜索是不可能很快求解的。根據(jù)動態(tài)規(guī)劃思想，如果我們已經(jīng)確定了某個位置(x,y)的最長滑行長度L，則與其相鄰的位置(x,y+1)如果能夠滑到(x,y)，則可以繼續(xù)滑行L長度。但是這意味著：要得到(x,y+1)的結(jié)果，必須先知道(x,y)的結(jié)果。（循環(huán)反復(fù)）。由于分支很多，事先確定并計算位置(x,y+1)對應(yīng)的各個的(x,y)形成悖論。（實際上也可以通過對高度排序后逐位置計算，但比較麻煩）記憶化搜索與區(qū)間動態(tài)規(guī)劃分析類比我們在前一例中的處理思路。由于對每個位置，他的最長滑行長度是唯一確定的，我們只要計算一次即可。如果用dp[x][y]記錄滑行長度，則有dp[x][y]=max(dp[x’][y’])+1（(x,y)與(x’,y’)相鄰且前者比后者高）之后如果有相鄰點再次滑到(x,y)，直接取用之前保存的結(jié)果即可。遞歸終點：該位置無法繼續(xù)滑行。f(5)f(3)f(4)f(1)f(2)f(2)f(3)f(1)f(2)f(4)f(2)f(3)f(1)f(2)f(6)記憶化搜索與區(qū)間動態(tài)規(guī)劃例6-15小結(jié)：每個位置的最優(yōu)滑行長度僅由周圍四個位置的高度和滑行長度所決定，因此需要訪問周圍四個點共四次（每個位置亦最多被遞歸進(jìn)入四次），一共n×m個位置，所以復(fù)雜度O(nm)。最優(yōu)子結(jié)構(gòu)如何體現(xiàn)？無后效性如何體現(xiàn)？重疊子問題如何體現(xiàn)？記憶化搜索與區(qū)間動態(tài)規(guī)劃例6-16：有排成一排的n堆石子，從左往右第i堆有di個石子。將相鄰兩堆石子進(jìn)行合并的代價為兩堆石子的石子個數(shù)之和。請設(shè)計一個方案將所有堆合并為一堆石子且代價最少（??不超過500）。比如初始有4堆石子，分別為d=[4,4,2,5]，此時可以先合并左邊兩個再合并右邊兩個得到d=[8,7]，再整體合并得到d=[15]，總代價為8+7+15=30。

記憶化搜索與區(qū)間動態(tài)規(guī)劃分析：很顯然，從樣例數(shù)據(jù)可以看出，直接貪心地優(yōu)先合并最小的是錯的。請自行驗證。記憶化搜索與區(qū)間動態(tài)規(guī)劃分析：由于石子是兩兩合并，所以在最終合并完成前，一定是兩堆。我們可以窮舉最后一步合并前，這兩堆的原始分界線，即：d1=[4]，d2=[4,2,5]d1=[4,4]，d2=[2,5]d1=[4,4,2]，d2=[5]記憶化搜索與區(qū)間動態(tài)規(guī)劃分析：總合并代價為分別將左側(cè)和右側(cè)合并為一堆的代價，以及最后將兩堆合并成一堆的代價。很顯然，在本題定義的合并代價下，后者是固定值，而前者需要在所有的劃分方案中選擇代價最小的一個。這樣，我們每遞歸一層，問題都會變小，直到最終求解。記憶化搜索與區(qū)間動態(tài)規(guī)劃分析：我們以將原數(shù)組切分為d1=[4]，d2=[4,2,5]為例：d2又可以切分為d21=[4],d22=[2,5]以及d21=[4,2],d22=[5]兩種，代價分別7+11=18和6+11=17。既然兩種方式都是合并成d2這一堆，代價盡量小比較優(yōu)。42542542525711426117+11=186+11=17記憶化搜索與區(qū)間動態(tài)規(guī)劃分析：求出d2=[4,2,5]的最小合并代價17后，繼續(xù)將d1=[4]，d2=[4,2,5]進(jìn)行合并，可得全部石子合并代價為17+15=32。同理可以得到d1=[4,4]，d2=[2,5]的最小代價為8+7+15=30。同理可以得到d1=[4,4,2]，d2=[5]的最小代價為16+15=31。則在各種切分d1、d2的方案中，選擇最優(yōu)的一個，總代價為30。42544254425417+15=3215+15=3016+15=31記憶化搜索與區(qū)間動態(tài)規(guī)劃分析：那么，如何記錄狀態(tài)呢？這題與前面的題目都不太一樣了，需要表述的是一段范圍，我們可以用dp[l][r]表示將l~r合并成一段所需的最小代價。這個區(qū)間的代價只在第一次被詢問到時需要計算，之后就可以直接調(diào)用了。要求解dp[l][r]，只需要枚舉所有的分?jǐn)辔恢?，找出左右子區(qū)間的合并代價和最小的方案即可，即：dp[l][r]=min(dp[l][x],dp[x+1][r])+sum(l~r)(l≤x<r)這里sum(l~r)表示最后一次將l~r合并成一堆石子的代價。遞歸終點：l==r。記憶化搜索與區(qū)間動態(tài)規(guī)劃例6-16小結(jié)：區(qū)間總共有約n2/2個，每個區(qū)間可能的分?jǐn)帱c為O(n)級別，所以復(fù)雜度O(n3)。最優(yōu)子結(jié)構(gòu)如何體現(xiàn)？無后效性如何體現(xiàn)？重疊子問題如何體現(xiàn)？記憶化搜索與區(qū)間動態(tài)規(guī)劃例6-17：有n堆石子排成一個圓圈，從順時針數(shù)第i堆有ai個石子。每次操作，將相鄰兩堆石子進(jìn)行合并的代價為兩堆石子的石子個數(shù)之和。請設(shè)計一個方案將所有相鄰堆合并為一堆石子且代價最?。╪不超過250）。合并次數(shù)是多少？記憶化搜索與區(qū)間動態(tài)規(guī)劃分析：很顯然合并次數(shù)是n-1，因此一定有一個相鄰關(guān)系未用于合并，直接枚舉這個位置（將其分?jǐn)喑纱?，可以得到正確的結(jié)果。但是復(fù)雜度是多少？記憶化搜索與區(qū)間動態(tài)規(guī)劃分析：可以發(fā)現(xiàn)，這樣的切斷，存在大量的重復(fù)計算，比如總長度為100，對比將100/1之間切斷的方案，與將1/2之間切斷的方案，從2~100范圍內(nèi)的所有區(qū)間其實都是一樣的，沒有必要重新求。1234989910012349899100597……記憶化搜索與區(qū)間動態(tài)規(guī)劃分析：如何能夠更好地利用這些數(shù)據(jù)呢。這涉及一個常用的處理環(huán)形的技巧，將環(huán)形切斷成串后，然后復(fù)制一份并拼接在原串后面。此時可以發(fā)現(xiàn)，這樣一個長