【正文】 個字符串可以插入、刪除、改變到另一個字符串，求改變的最小步驟。(i1)==(i+j1)) array[i][j] = true。(j1)==(i+j1)||array[i1][j]amp。核心的Java代碼：if(array[i][j1]amp。我們定義一個布爾類型的二維數(shù)組 array,array[i][j]表示str1[i]和str2[j]能否組成str[i+j].i=0或者j=0表示空字符串，所以初始化時(shí)，array[0][j]表示str1的前j個字符是否和str都匹配。opt[num2][num1]即為所求結(jié)果。39。i=num2。,a[i1])。i++) opt[0][i] = opt[0][i1]+table(39。NullAGTGATGNull3568111214G2T3T4A7G9第0行，第0列表示null和字符串匹配情況，結(jié)果是’’和各個字符的累加： for(i=1。39。39。用二維數(shù)組opt[i][j]記錄字符串a(chǎn)中的前i個字符與字符串b中的前j個字符匹配所產(chǎn)生的最大值。這題有點(diǎn)像求最長公共子序列。核心的Java代碼為：totalLCS(string,new StringBuffer(string).reverse().toString())。是S的反串)的最長公共子串其實(shí)一定是回文的。通過這樣的結(jié)論可以和最長公共子串聯(lián)系起來(未證明)：S和S39。帶有詳細(xì)注釋的代碼可以在。在求最優(yōu)解時(shí)，順著箭頭從后向前尋找公共字串的序號，記錄下來，輸出即可。帶有詳細(xì)注釋的代碼可以在Pku acm 2250 Compromise 動態(tài)規(guī)劃題目總結(jié)(六)這個也是求最長公共字串，只是相比Common Subsequence需要記錄最長公共字串的構(gòu)成，此時(shí)箭頭的標(biāo)記就用上了,在程序中，用opt[][]存放標(biāo)記，0表示朝向左上方，1表示指向上，1表示指向左。 else result[i][j]= = result[i1][j]result[i][j1]?result[i1][j]:result[i][j1]。j=length2。i=length1。i++){ result[0][i] = 0。}for(int i=0。ilength1。我們定義result[i][j]表示Xi和Yj 的最長子串(LCS).當(dāng)i或j等于0時(shí)，result[i][j]=0. LCS問題存在一下遞歸式：result[i][j] = 0 i=0 or j=0result[i][j] = result[i1][j1]+1 Xi= =Yjresult[i][j] = MAX(result[i1][j], result[i][j1]) Xi! =Yj對于以上例子，算法如下：Result[i][j]:abcfba012345600000000a10111111b20122222f30122333c40123333a50123334從最后一個格向上順著箭頭的方向可以找到最長子串的構(gòu)成，在有箭頭組成的線段中，含有斜向上的箭頭對應(yīng)的字符是其中的一個lcs。下面以題目中的例子來說明算法：兩個string分別為：abcfbc和abfca。帶有詳細(xì)注釋的代碼可以在Pku acm 1458 Common Subsequence 動態(tài)規(guī)劃題目總結(jié)(五)求兩個string的最大公共字串，動態(tài)規(guī)劃的經(jīng)典問題。}我們可以繼續(xù)找出規(guī)律，其實(shí)這個就是斐波那切數(shù)列數(shù)列：F[N] = F[N1]+F[N2]。i++){ array[i][0] = array[i1][1]。for(i=2。array[1][1] = 1。先分析一下這個問題：N以1結(jié)尾的個數(shù)以0結(jié)尾的個數(shù)總和111221233………對于n=1來說，以1結(jié)尾、以0結(jié)尾個數(shù)都是1，總和是2，下面過度到2：對于所有以1結(jié)尾的數(shù)，后面都可以加上0，變?yōu)閚=2時(shí)以0結(jié)尾的，而只有結(jié)尾為0的數(shù)才能加上1（因?yàn)椴荒苡袃蓚€連續(xù)0），這樣就可以在n=2的格里分別填上2，總和算出來為3，以此類推，我們可以算出所有n=45的值，然后根據(jù)輸入進(jìn)行相應(yīng)輸出。 }}帶有詳細(xì)注釋的代碼可以在Pku acm 1953 World Cup Noise 動態(tài)規(guī)劃題目總結(jié)(四)給定一個小于45的整數(shù)n，求n位2進(jìn)制數(shù)中不含相鄰1的數(shù)的個數(shù)。 } else { result[i] = result[i1]+i。flag[result[i1]i]==false) { result[i] = result[i1]i。i++){ if(result[i1]i0amp。核心的java代碼為：for(i=1。帶有詳細(xì)注釋的代碼可以在Pku acm 2081 Recaman39。 }}帶有詳細(xì)注釋的代碼可以在Pku acm 1579 Function Run Fun 動態(tài)規(guī)劃題目總結(jié)(二)Consider a threeparameter recursive function w(a, b, c): if a = 0 or b = 0 or c = 0, then w(a, b, c) returns: 1 if a 20 or b 20 or c 20, then w(a, b, c) returns: w(20, 20, 20) if a b and b c, then w(a, b, c) returns: w(a, b, c1) + w(a, b1, c1) w(a, b1, c) otherwise it returns: w(a1, b, c) + w(a1, b1, c) + w(a1, b, c1) w(a1, b1, c1)這本身就是一個遞歸函數(shù)，要是按照函數(shù)本身寫遞歸式，結(jié)果肯定是TLE，這里我開了一個三維數(shù)組，從w(0,0,0)開始遞推，逐步產(chǎn)生到w(20,20,20)的值，復(fù)雜度O(n^3).總結(jié)：這道題是很地道的DP，因?yàn)樗淖訂栴}實(shí)在是太多了，所以將問題的結(jié)果保存起來，劉汝佳《算法藝術(shù)和信息學(xué)競賽》中115頁講到自底向上的遞推，這個例子就非常典型。j=i。i=0。Pku acm 1163 the Triangle 動態(tài)規(guī)劃題目總結(jié)(一)題目：對于一個有數(shù)字組成的二叉樹，求由葉子到根的一條路徑，使數(shù)字和最大，如： 73 8 8 1 02 7 4 4 4 5 2 6 5這個是經(jīng)典的動態(tài)規(guī)劃，也是最最基礎(chǔ)、最最簡單的動態(tài)規(guī)劃，典型的多段圖。思路就是建立一個數(shù)組，由下向上動態(tài)規(guī)劃，保存頁子節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最大值，Java核心代碼如下：for(int i=num2。i){ for(int j=0。j++){ //該句是整個動態(tài)規(guī)劃的核心number[i][j]=(number[i+1][j],number[i+1][j+1])+number[i][j]。總體來說這個題目還是非常簡單的，不過這個思想是地道的動態(tài)規(guī)劃。s Sequence 動態(tài)規(guī)劃題目總結(jié)(三)一道很簡單的動態(tài)規(guī)劃，根據(jù)一個遞推公式求一個序列，我選擇順序的求解，即自底向上的遞推，一個int數(shù)組result根據(jù)前面的值依此求出序列的每一個結(jié)果，另外一個boolean數(shù)組flag[i]記錄i是否已經(jīng)出現(xiàn)在序列中，求result的時(shí)候用得著，這樣就避免了查找。i=500000。amp。 flag[result[i1]i] = true。 flag[result[i1]+i] = true。看似簡單的一道題，如果當(dāng)n=45時(shí)，對2的45次方檢查，是無法完成的任務(wù)。核心代碼如下：int i,num,count,array[50][2],j=0。array[1][0] = 1。i50。 array[i][1] = array[i1][1]+array[i1][0]?？梢岳^續(xù)簡化代碼。算法導(dǎo)論有詳細(xì)的講解。創(chuàng)建一個二維數(shù)組result[][],維數(shù)分別是兩個字符串長度加一。Ja