提高篇動態(tài)規(guī)劃專題

1、提高篇動態(tài)規(guī)劃專題動態(tài)規(guī)劃 遞歸遞歸 遞推遞推一種精妙的算法思想。特點： 沒有固定的寫法 具體問題具體分析需要： 多練習、多思考、多總結(jié)什么是動態(tài)規(guī)劃最優(yōu)化問題1 1復雜問題2 2分解子問題3 3記錄每個解4 4dynamic programming 動態(tài)規(guī)劃是一種用來解決一類最優(yōu)化問題最優(yōu)化問題的算法思想。將一個復復雜的問題雜的問題分解成若干個子問題子問題，通過綜合子問題的最優(yōu)解來得到原問題的最優(yōu)解。動態(tài)規(guī)劃會將每個求解過的子問題的解記錄下來解記錄下來，這樣可以提高計算效率，但不不能說這種做法就是是動態(tài)規(guī)劃的核心核心。動態(tài)規(guī)劃的遞歸寫法【理解】如何記錄子問題的解，來避免下次遇到相同的子問題時

2、的重復計算。斐波那契數(shù)列：f0=1,f1=1,fn=fn-1+fn-2(n=2)int f(int n) if (n=0|n=1) return 1; else return f(n-1)+f(n-2); 一般可以使用遞歸或者遞推的寫法來實現(xiàn)動態(tài)規(guī)劃，其中遞歸寫法在此處又稱作記憶化搜索記憶化搜索。缺點：重復計算。當n=5時，f(5)=f(4)+f(3),接下來計算f(4)=f(3)+f(2),這樣f(3)就被計算了兩次。如果n很大，時間復雜度會高達o(2n)。避免重復計算 開一個一維數(shù)組dp，用于保存已經(jīng)計算過的結(jié)果，其中dpn記錄f(n)的結(jié)果，并用dpn=-1表示f(n)當前還沒有被計算過

3、。int dpmaxn;int f(int n) if (n=0|n=1) return 1; /遞歸邊界 if (dpn!=-1) return dpn; /已經(jīng)計算過，直接返回結(jié)果，不再重復計算 else dpn=f(n-1)+f(n-2); /計算f(n)，并保存至dpn return dpn; /返回f(n)的結(jié)果 記憶化搜索記憶化搜索時間復雜度時間復雜度o(2n)降到了降到了o(n)時間復雜度對比圖f(5)f(4)f(3)f(2)f(1)f(0)f(1)f(2)f(1)f(0)f(3)f(2)f(1)f(0)f(1)斐波那契數(shù)列遞歸圖o(2n)f(5)f(4)f(3)f(2)f(1)

4、f(0)f(1)f(2)f(3)斐波那契數(shù)列記憶化搜索o(n)重疊子問題（overlapping subproblems） 如果一個問題可以被分解為若干個子問題，且這些子問題會重復出現(xiàn)，那么就稱這個問題擁有重疊子問題。 一個問題必須擁有重疊子問題重疊子問題，才能使用動態(tài)規(guī)劃動態(tài)規(guī)劃去解決。動態(tài)規(guī)劃的遞推寫法【數(shù)塔問題】將一些數(shù)字排成數(shù)塔的形狀，其中第一層有一個數(shù)字，第二層有兩個數(shù)字第n層有n個數(shù)字。現(xiàn)在要從第一層走到第n層，每次只能走向下一層連接的兩個數(shù)字中的一個，問：最后將路徑上所有數(shù)字相加后得到的和最大是多少？5837124910516113694動態(tài)規(guī)劃的遞推寫法 如果開一個二維數(shù)組f，

5、其中fij存放第i層的第j個數(shù)字，那么就有f11=5,f21=8,f22=3,f31=12,f54=9,f55=4。 如果嘗試窮舉所有路徑，然后記錄路徑上的數(shù)字和的最大值，那么由于每層中的每個數(shù)字都會有兩條分支路徑，因此時間復雜度為o(2n)，這在n很大的情況下是不可以接受的。那么，產(chǎn)生這么大復雜度的原因原因是什么？ 從5出發(fā)，按587的路線來到7，并枚舉從從7出發(fā)的到達最底層的所有路徑出發(fā)的到達最底層的所有路徑。但是，之后當按537的路線再次來到7時，又會去枚舉從從7出發(fā)的到達最底層的出發(fā)的到達最底層的所有路徑所有路徑，這就導致了從從7出發(fā)的到達最底層的所有路徑出發(fā)的到達最底層的所有路徑都被

6、反復反復地訪問。其實，可以把路徑上能產(chǎn)生的最大和記錄下來，這樣就可以避免重復計算。 所以令dpij表示從第i行第j個數(shù)字出發(fā)的到達最底層的所有路徑中能得到的最大和，例如dp32就是7的最大和。那么dp11就是最終答案，現(xiàn)在想辦法求求出出它。 注意一個細節(jié)：如果要求出“從位置（1,1）到達最底層的最大和”dp11，那么一定要先求出它的兩個子問題“從位置（2,1）到達最底層的最大和dp21”和“從位置（2,2）到達最底層的最大和dp22”，即進行了一次決策決策：走數(shù)字5的左下還是右下。于是dp11就是dp21和dp22的較大值加上5。公式：dp11=max(dp21,dp22)+f11動態(tài)規(guī)劃的遞

7、推寫法 歸納：如果要求出dpij，那么一定要求出它的兩個子問題“從位置(i+1,j)到達最底層的最大和dpi+1j”和“從位置(i+1,j+1)到達最底層的最大和dpi+1j+1”，即進行了一次決策決策：走位置(i,j)的左下還是右下。公式：dpij=max(dpi+1j,dpi+1j+1)+fij 把dpij稱為問題的狀態(tài)狀態(tài)，公式稱為狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程，它把狀態(tài)dpij轉(zhuǎn)移為dpi+1j和dpi+1j+1?？梢园l(fā)現(xiàn)，狀態(tài)dpij只與第i+1層的狀態(tài)有關，而與其他層的狀態(tài)無關。那么如果總是將層號增大，什么時候會到頭呢？其實，數(shù)塔的最后一層的dp值總是等于元素本身，即dpnj=fnj(1

8、=j=n)，把這種可以直接確定其結(jié)果的部分稱為邊界邊界，而動態(tài)規(guī)劃的遞推遞推寫法總是從這些邊界出發(fā)，通過狀態(tài)轉(zhuǎn)移方程擴散到整個dp數(shù)組。 這樣就可以從最底層各位置的dp值開始，不斷往上上求出每一層各位置的dp值，最后就會得到dp11，即為想要的答案。動態(tài)規(guī)劃的遞推寫法（代碼）#include#includeusing namespace std;const int maxn=1000;int fmaxnmaxn,dpmaxnmaxn;int main() int n; cinn; for(int i=1;i=n;i+) for(int j=1;jfij; /輸入數(shù)塔 for(int j=1;j

9、=1;i-) for(int j=1;j=i;j+) dpij=max(dpi+1j,dpi+1j+1)+fij; /動態(tài)轉(zhuǎn)移方程 coutdp11endl;return 0; 動態(tài)規(guī)劃的遞推寫法 輸入數(shù)據(jù)558 312 7 164 10 11 69 5 3 9 4 輸出結(jié)果44動態(tài)規(guī)劃的遞推寫法對比遞歸和遞推寫法：遞歸遞歸也可實現(xiàn)（即從dp11開始遞歸，直至到達邊界時返回結(jié)果）。是自頂向下自頂向下（top-down approach），即從目標問題開始，將它分解成子問題的組合，直到分解至邊界為止。遞推遞推是從底向上從底向上（bottom-up approach），即從邊界開始，不斷向上解決問

10、題，直到解決了目標問題。概念概念：如果一個問題的最優(yōu)解可以由其子問題的最優(yōu)解有效地構(gòu)造出來，那么稱這個問題擁有最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)（optimal substructure）?？梢允褂脛討B(tài)規(guī)劃的條件一個問題必須擁有重疊子問題重疊子問題和最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)，才能使用動態(tài)規(guī)劃動態(tài)規(guī)劃去解決。分治與動態(tài)規(guī)劃 相同點：將問題分解為子問題，然后合并子問題的解得到原問題的解。 不同點：分治分治的子問題不重疊不重疊。動態(tài)規(guī)劃動態(tài)規(guī)劃的問題擁有重疊重疊子問題。例如：歸并排序和快速排序都分別處理左序列和右序列，然后將左右序列的結(jié)果合并，過程中不出現(xiàn)重疊子問題，因此他們使用的都是分治法。另外，分治法解決的問題不

11、一定是最優(yōu)化問題，而動態(tài)規(guī)劃解決的問題一定是最優(yōu)化問題。貪心與動態(tài)規(guī)劃 相同點：要求原問題必須有最優(yōu)子結(jié)構(gòu)。 不同點：貪心法的計算方式“自頂向下”，但并不等待子問題求解完畢后再選擇使用哪一個，而是通過一種策略直接選擇一個子問題去求解，沒被選擇的子問題直接拋棄。這種所謂“最優(yōu)選擇”的正確性需要用歸納法證明。而動態(tài)規(guī)劃不管是采用自底向上還是自頂向下的計算方式，都是從邊界開始向上得到目標問題的解（即考慮所有子問題）。貪心：壯士斷腕的決策，只要選擇，絕不后悔。貪心：壯士斷腕的決策，只要選擇，絕不后悔。動態(tài)規(guī)劃：要看哪個選擇笑到最后，暫時領先說明不了問題。動態(tài)規(guī)劃：要看哪個選擇笑到最后，暫時領先說明不了

12、問題。最大連續(xù)子序列和【問題描述】 給定一個數(shù)字序列a1,a2,an,求i,j(1=i=j=n),使得ai+aj最大，輸出這個最大和。【樣例】輸入：-2 11 -4 13 -5 -2輸出：20步驟1：令狀態(tài)dpi表示以ai作為末尾的連續(xù)序列的最大和（ai必須作為末尾）。那么dp0=-2 dp1=11 dp2=7 (11+(-4)=7) dp3=20 (11+(-4)+13=20) dp4=15 (11+(-4)+13+(-5)=15) dp5=13 (11+(-4)+13+(-5)+(-2)=13)于是轉(zhuǎn)換成求dp0,dp1,dpn-1中的最大值，想辦法求解dp數(shù)組。原序列：原序列：-2 11

13、 -4 13 -5 -2步驟2：因為dpi以ai結(jié)尾的連續(xù)序列，那么只有兩種情況： 這個最大和的連續(xù)序列只有一個元素，即ai。dpi=ai 這個最大和的連續(xù)序列有多個元素，即從前面某處ap開始(pi)，一直到ai結(jié)尾。dpi=dpi-1+ai 狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：dpi=maxai,dpi-1+ai 邊界dp0=a0，從小到大枚舉i，即可得到整個dp數(shù)組。#include#include#include#includeusing namespace std;const int maxn=10010;int amaxn,dpmaxn;/ai存放序列，dpi存放以ai結(jié)尾的連續(xù)序列的最大和

14、int main() int n; scanf(%d,&n);/cinn; for(int i=0;iai; /邊界 dp0=a0; for(int i=1;in;i+) /狀態(tài)轉(zhuǎn)移方程 dpi=max(ai,dpi-1+ai); /dpi存放以ai結(jié)尾的連續(xù)序列的最大和，需要遍歷i得到最大的才是結(jié)果 int k=0; for(int i=1;idpk) k=i; printf(%dn,dpk);/coutdpk)endl; system(pause); return 0;狀態(tài)的無后效性 當前狀態(tài)記錄了歷史信息，一旦當前狀態(tài)確定，就不會再改變，且未來的決策只能在已有的一個或若干個狀態(tài)的基礎上進

15、行，歷史信息只能通過已有的狀態(tài)去影響未來的決策。 即每次計算狀態(tài)dpi，都只會設計dpi-1，而不直接用到dpi-1蘊含的歷史信息。動態(tài)規(guī)劃核心 對動態(tài)規(guī)劃可解的問題來說，總會有很多設計狀態(tài)的方式，但并不是所有狀態(tài)都具但并不是所有狀態(tài)都具有無后效性有無后效性，因此必須設計一個擁有無后效性的狀態(tài)以及相應的狀態(tài)轉(zhuǎn)移方程，否則動態(tài)規(guī)劃就沒有辦法得到正確結(jié)果。事實上，如何設計狀態(tài)和狀態(tài)轉(zhuǎn)移方程，才如何設計狀態(tài)和狀態(tài)轉(zhuǎn)移方程，才是動態(tài)規(guī)劃的核心，而它們也是動態(tài)規(guī)劃是動態(tài)規(guī)劃的核心，而它們也是動態(tài)規(guī)劃最難的地方最難的地方。問題 a: 最大連續(xù)子序列（時間限制: 1 sec 內(nèi)存限制: 32 mb）題目描述

16、給定k個整數(shù)的序列 n1, n2, ., nk ，其任意連續(xù)子序列可表示為 ni, ni+1, ., nj ，其中 1 = i = j = k。最大連續(xù)子序列是所有連續(xù)子序列中元素和最大的一個，例如給定序列 -2, 11, -4, 13, -5, -2 ，其最大連續(xù)子序列為 11, -4, 13 ，最大和為20?，F(xiàn)在增加一個要求，即還需要輸出該子序列的第一個和最后一個元素。輸入測試輸入包含若干測試用例，每個測試用例占2行，第1行給出正整數(shù)k( k= 10000 )，第2行給出k個整數(shù)，中間用空格分隔，每個數(shù)的絕對值不超過100。當k為0時，輸入結(jié)束，該用例不被處理。輸出對每個測試用例，在1行里

17、輸出最大和、最大連續(xù)子序列的第一個和最后一個元素，中間用空格分隔。如果最大連續(xù)子序列不唯一，則輸出序號i和j最小的那個（如輸入樣例的第2、3組）。若所有k個元素都是負數(shù)，則定義其最大和為0，輸出整個序列的首尾元素。 樣例輸入 5 -3 9 -2 5 -4 3 -2 -3 -1 0 樣例輸出 12 9 5 0 -2 -1提示（較難） 首先可以想到的做法是枚舉每個區(qū)間的和，預處理sumi來表示區(qū)間1, i的和之后通過減法我們可以o(1)時間獲得區(qū)間i, j的和，因此這個做法的時間復雜度為o(n2)。 然后這題的數(shù)據(jù)范圍較大，因此還需作進一步優(yōu)化才可以ac。記第i個元素為ai，定義dpi表示以下標i

18、結(jié)尾的區(qū)間的最大和，那么dpi的計算有2種選擇，一種是含有ai-1，一種是不含有ai-1，前者的最大值為dpi-1+ai，后者的最大值為ai。而兩者取舍的區(qū)別在于dpi-1是否大于0。最長不下降子序列（lis）【問題描述】 在一個數(shù)字序列中，找到一個最長的子序列（可以不連續(xù)），使得這個子序列是不下降（非遞減）的?！緲永枯斎耄? 1 2 3 -1 -2 7 9輸出：5（長度）/即1 2 3 7 9 令dpi表示以ai結(jié)尾的最長不下降子序列長度（和最大連續(xù)子序列和問題一樣，以ai結(jié)尾是強制的要求）。這樣對ai倆說就會有兩種可能：（1）如果存在ai之前的元素sj(ji)，使得ajdpi（即把ai跟

19、在以aj結(jié)尾的lis后面時能比當前以ai結(jié)尾的lis長度更長），那么就把ai跟在以aj結(jié)尾的lis后面，形成一條更長的不下降子序列（令dpi=dpj+1）。（2）如果ai之前的元素都比ai大，那么ai就只好自己形成一條lis，但是長度為1，即這個子序列里面只有一個ai。最后以ai結(jié)尾的lis長度就是（1）（2）中能形成的最大長度。狀態(tài)轉(zhuǎn)移方程 dpi=max1,dpj+1(j=1,2,i-1&ajai)其中隱含了邊界：dpi=1(1=i=n)時間復雜度o(n2)#include#includeusing namespace std;const int n=100;int an,dpn;int

20、main() int n; cinn; for(int i=1;iai;int ans=-1; /記錄最大的dpi for(int i=1;i=n;i+) /按順序計算出dpi的值 dpi=1; /邊界初始條件（即先假設每個元素自成一個子序列） for(int j=1;j=aj&(dpj+1dpi) dpi=dpj+1; /狀態(tài)轉(zhuǎn)移方程，用以更新dpi ans=max(ans,dpi); coutansendl; return 0;問題 a: 最長上升子序列（ 2 sec 64 mb）題目描述一個數(shù)列ai如果滿足條件a1 a2 . an，那么它是一個有序的上升數(shù)列。我們?nèi)?shù)列(a1, a2,

21、., an)的任一子序列(ai1, ai2, ., aik)使得1 = i1 i2 . ik = n。例如，數(shù)列(1, 7, 3, 5, 9, 4, 8)的有序上升子序列，像(1, 7)， (3, 4, 8)和許多其他的子序列。在所有的子序列中，最長的上升子序列的長度是4，如(1, 3, 5, 8)。 現(xiàn)在你要寫一個程序，從給出的數(shù)列中找到它的最長上升子序列。輸入輸入包含兩行，第一行只有一個整數(shù)n（1 = n = 1000），表示數(shù)列的長度。第二行有n個自然數(shù)ai，0 = ai = 10000，兩個數(shù)之間用空格隔開。輸出輸出只有一行，包含一個整數(shù)，表示最長上升子序列的長度。樣例輸入7 1 7

22、3 5 9 4 8樣例輸出4最長公共子序列（lcs） 給定兩個字符串（或數(shù)字序列）a和b，求一個字符串，使得這個字符串是a和b的最長公共部分（子序列可以不連續(xù)）。 樣例： 如樣例所示，字符串“sadstory”與“adminsorry”的最長公共子序列為“adsory”，長度為6。 令dpij表示字符串a(chǎn)的i號位和字符串b的j號位之前的lcs長度（下標從1開始），如dp45表示“sads”與“admin”的lcs長度。那么可以根據(jù)ai和bj的情況，分為兩種決策：（1）若ai=bj，則字符串a(chǎn)與字符串b的lcs增加了1位，即有dpij=dpi-1j-1+1。（2）若ai!=bj，則字符串a(chǎn)的i號位和字符串b的j號位之前的lcs無法延長，因此dpij將會繼承dpi-1j與dpij-1中的較大值，即有dpij=maxdpi-aj，dpij-1。狀態(tài)轉(zhuǎn)移方程： 邊界：dpi0=dp0j=0(0=i=n,0=i=m)時間復雜度：o(nm)輸入數(shù)據(jù)：sadstoryadminsorry輸出結(jié)果：6最長回文子串給出一個字符串s，求s的最長回文子串的長度。樣例：字符串“patzjujztaccbcc”的最長回文子串為“atzjujzta”，長度為9。最長回文子串是否能轉(zhuǎn)換為最長公共子序列（是否能轉(zhuǎn)換為最長公共子序列（