利用動(dòng)態(tài)規(guī)劃算法解決最長(zhǎng)公共子序列問題摘要：算法可以理解為有基本運(yùn)算及規(guī)定的運(yùn)算順序所構(gòu)成的完整的解題步驟?；蛘呖闯砂凑找笤O(shè)計(jì)好的有限的確切的計(jì)算序列，并且這樣的步驟和序列可以解決一類問題。其中動(dòng)態(tài)規(guī)劃是一種有效的解決問題的算法。此論文將圍繞如何利用動(dòng)態(tài)規(guī)劃算法解決最長(zhǎng)公共子序列問題展開。關(guān)鍵詞：算法，動(dòng)態(tài)規(guī)劃，最長(zhǎng)公共子序列。Abstract:Algorithmcanbeunderstoodasabasiccomputingandtheprovisionsoftheorderofoperationsthatformacompletesolvingsteps.Orasaccordingtotherequestanddesignoftheexactcalculationofgoodlimitedsequence,andthestepsandcansolveproblemofsequence.Amongthemthedynamicplanningisakindofeffectiveproblemsolvingalgorithm.Thispaperwillfocusonhowtousedynamicprogrammingalgorithmispresentedtosolvethelongestpublicsononsequence.Keywords:algorithm,thedynamicprogramming,thelongestpublicsonsequence.1引言動(dòng)態(tài)規(guī)劃算法是一種有效的解決問題的算法。通常將待求解問題分解成若干個(gè)子問題，利用這一特性，可以解決很多能夠以大化小的問題，如：矩陣連成問題、求最長(zhǎng)公共子序列、求凸多邊形最優(yōu)三角剖分、圖像壓縮、電路布線、流水作業(yè)調(diào)度等。此論文將聯(lián)系如何求解最長(zhǎng)公共子序列來(lái)描述動(dòng)態(tài)規(guī)劃算法。2動(dòng)態(tài)規(guī)劃的思想2、1動(dòng)態(tài)規(guī)劃的概念動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題。但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。不同子問題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。如果能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。

找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。2、3動(dòng)態(tài)規(guī)劃算法的基本要素最優(yōu)子結(jié)構(gòu)矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后再設(shè)法說(shuō)明在這個(gè)假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個(gè)問題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問題能用動(dòng)態(tài)規(guī)劃算法求解的前提。重疊子問題遞歸算法求解問題時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。這種性質(zhì)稱為子問題的重疊性質(zhì)。動(dòng)態(tài)規(guī)劃算法，對(duì)每一個(gè)子問題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此子問題時(shí)，只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。通常不同的子問題個(gè)數(shù)隨問題的大小呈多項(xiàng)式增長(zhǎng)。因此用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間，從而獲得較高的解題效率。備忘錄方法備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個(gè)解過(guò)的子問題建立了備忘錄以備需要時(shí)查看，避免了相同子問題的重復(fù)求解。3、利用動(dòng)態(tài)規(guī)劃算法解決求最長(zhǎng)公共子序列問題

3、1問題描述?若給定序列X={x1,x2,…,xm},則另一序列Z={z1,z2,…,zk},是X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列{ii,i2,...,ik}使得對(duì)于所有j=1,2,…,k有：zj=xij。例如，序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列，相應(yīng)的遞增下標(biāo)序列為{2,3,5,7}。?給定2個(gè)序列X和Y,當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。3、2最長(zhǎng)公共子序列的結(jié)構(gòu)設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長(zhǎng)公共子序列為Z={z1,z2,…，zk},則⑴若xm=yn,^0zk=xm=yn，且zk-1是xm-1和yn-1的最長(zhǎng)公共子序列。⑵若xm尹yn且zk尹xm，則Z是xm-1和Y的最長(zhǎng)公共子序列。⑶若xm尹yn且zk尹yn，則Z是X和yn-1的最長(zhǎng)公共子序列。由此可見，2個(gè)序列的最長(zhǎng)公共子序列包含了這2個(gè)序列的前綴的最長(zhǎng)公共子序列。因此，最長(zhǎng)公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。3、3子問題的遞歸結(jié)構(gòu)由最長(zhǎng)公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列和的最長(zhǎng)公共子序列的長(zhǎng)度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…，yj}。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列。故此時(shí)C[i][j]=0。其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下:0,j=0由于在所考慮的子問題空間中，總共有e(mn)個(gè)不同的子問題，因此，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。c[I-1][j-1]+1l,jmax{c[I][j-1],c[l-1][j]}l,jyj0;x。yjc[I-1][j-1]+1l,jmax{c[I][j-1],c[l-1][j]}l,jyj0;x。yj?如果只需要計(jì)算最長(zhǎng)公共子序列的長(zhǎng)度，則算法的空間需求可大大減少。事實(shí)上，在計(jì)算c[i][j]時(shí)，只用到數(shù)組c的第i行和第i-1行。因此，用2行的數(shù)組空間就可以計(jì)算出最長(zhǎng)公共子序列的長(zhǎng)度。進(jìn)一步的分析還可將空間需求減至O(min(m,n))。4、結(jié)束語(yǔ)通過(guò)對(duì)動(dòng)態(tài)規(guī)劃算