dp算法思想和運用實踐例題(編輯修改稿)
2025-07-04 13:33 本頁面
【文章內容簡介】 ]） break。 d[j+1]=h[i]。 if（j==c1）c++。 }printf（%d\n,c）。} 〖案例2〗公共子序列子序列是給定序列的部分（或者沒有）元素組成。給定的序列X = x1, x2, ..., xm ，另一個序列Z= z1, z2, ..., zk是X的子序列，如果存在嚴格遞增X的序號序列 i1, i2, ..., ik，對于所有的j = 1,2,...,k, 。例如Z = a, b, f, c 是X = a, b, c, f, b, c 的子序列，對應在X中的序號為 1, 2, 4, 6 。給定兩個序列X和Y，找到X和Y的最長的公共子序列的長度。每組測試數(shù)據(jù)包含兩個字符串表示給定的序列，中間用空格隔開。對于每個測試數(shù)據(jù)，輸出最長的公共子序列的長度。abcfbc abfcabprogramming contest abcd mnp420動態(tài)規(guī)劃求解令 X0 = 216。 Xi ={x1,x2,…,xi},1≤i≤m Xm = X Y0 = 216。 Yi ={y1,y2,…,yi},1≤i≤n Yn = YLCS(Xi,Yj)表示(Xi,Yj)的最長公共子序列長度，則有：一般有：含義：① 若xm=yn=z(或xi=yj=z)則xm，yn必包含在LCS(Xm,Yn)中。則， LCS(Xm,Yn) = LCS(Xm1,Yn1)∪{z} ② 若xm≠yn，則xm，yn中至少有一個不會包含在LCS(Xm,Yn)中，則， LCS(Xm,Yn)等于LCS(Xm1,Yn)和LCS(Xm,Yn1)中長的一個③ 若i=0或j=0,則其中一個（Xm或Yn）為空集合，此時LCS(Xm,Yn)= 216。遞推過程：為求LCS(Xi,Yj),需要首先得到LCS(Xi1,Yj1)或LCS(Xi1,Yj)和LCS(Xi,Yj1)的值。故遞推過程如下：從i=0或j=0算起，對所有i≤m的每個值，求j=1…n的所有可能的LCS(Xi,Yj)例：令X={a,b,c,f,b,c}， Y={a,b,f,c,a,b } LCSYabfcabj i 0123456X00000000a10111111b20122222c30122333f40123333b50123334c60123444|LCS（X,Y）| = 4（表格右下腳的值）反向推導，求出LCS（X,Y）＝ {a,b,c,b}/{a,b,f,c}整個求解過程就可以用填寫一個最長公共子序列長度值的二維表來描述，表中第（i,j）處的值就是Xi與Yj的最長公共子序列長度值。填表的過程就是根據(jù)遞推關系，從1行1列開始，以行或者列優(yōu)先的順序，依次填寫表格，最后根據(jù)整個表格的數(shù)據(jù)通過簡單的取舍求得最長公共子序列長度。二維表需要的存儲空間為O(m*n)，在需要處理的字符串較長時，需要的空間比較大。注意到在填表過程中，填寫第i行（列）時，前面i2行（列）的數(shù)據(jù)不參與運算，為了節(jié)省存儲空間，我們使用滾動數(shù)組：只保留當前填寫的行（列）及前一行（列）的值，這樣只需要兩個一維數(shù)組即可，當前行填寫完畢，向后滾動。int main（）{char s1[1000],s2[1000]。 //輸入兩個字符串序列int r[1000],s[1000]。 //DP記錄狀態(tài)轉移結果，采用滾動數(shù)組節(jié)省空間int l1,l2,i,j。 //l1,l2記錄兩個字符串的長度while（scanf（%s%s,s1,s2）!=EOF） {l1=strlen（s1）。 l2=strlen（s2）。 for（i=0。i=l2。++i）r[i]=0。 for（i=0。il
教學教案相關推薦
鄂ICP備17016276號-1