最近朋友讓幫做個關于動态規劃的最長公共子序列的問題,翻看以前的筆記并完成該題後,順便寫這樣一篇文章,希望對大家有所幫助,同時也幫助自己回顧該知識點.
子序列:若給定序列x={x1,x2,…,xm},則另一序列z={z1,z2,…,zk},是x的子序列是指存在一個嚴格遞增下标序列{i1,i2,…,ik}使得對于所有j=1,2,…,k有:zj=xij.
公共子序列:給定2個序列x和y,當另一序列z既是x的子序列又是y的子序列時,稱z是序列x和y的公共子序列.
最長公共子序列:給定2個序列x={x1,x2,…,xm}和y={y1,y2,…,yn},找出x和y的最長公共子序列.
如：序列abcdef和adfgh的最長公共子序列為adf
注意:最長公共子串(longest common substirng)和最長公共子序列(longest common subsequence,簡稱lcs)的差別為是最長公共子串的串是一個連續的部分,而最長公共子序列則是從不改變序列的順序,而從序列中去掉任意的元素而獲得新的序列;通俗的說就是子串中字元的位置必須是連續的而子序列則可以不必連續.
設序列x={x1,x2,…,xm}和y={y1,y2,…,yn}的最長公共子序列為z={z1,z2,…,zk} ,則
(1)若xm=yn,則zk=xm=yn,且z1,z2,…, zk-1是否為x1,x2,…,xm-1和y1,y2,…,yn-1的最長公共子序列.
(2)若xm≠yn且zk≠xm,則z是x1,x2,…,xm-1和y的最長公共子序列.
(3)若xm≠yn且zk≠yn,則z是x和y1,y2,…,yn-1的最長公共子序列.
由此可見,2個序列的最長公共子序列包含了這2個序列的字首的最長公共子序列.是以,最長公共子序列問題具有最優子結構性質.當問題具有最優子結構性質和子問題重疊性質時就可以用動态規劃算法解決該問題.
由最長公共子序列問題的最優子結構性質建立子問題最優值的遞歸關系.用c[i][j]記錄序列和的最長公共子序列的長度.其中,xi={x1,x2,…,xi},yj={y1,y2,…,yj}.當i=0或j=0時,空序列是xi和yj的最長公共子序列.故此時c[i][j]=0.其它情況下,由最優子結構性質可建立遞歸關系如下:
其對應的核心代碼如下:
例如:輸入字元串“bdcaba”和"abcbdab",求它們的最長公共子序列長度.在《算法設計與分析》課程中我們老師講述的方法通常是使用動态規劃填充表格方法解決.初始時,x字元串的長度為m,y字元串的長度為n.c[m,n]二位數組如上面遞歸關系遞歸,最後的c[m,n]為最大數字即最長公共子序列的長度.
其中從表中找出最長公共子序列的方法
(1) 從(m,n)到(0,0)
(2) 若目前格與左邊一格相同,則畫" 一";若目前格與上邊一格相同,則畫"|";上兩者都不符合,從目前格到左上格化斜線箭頭"\";
(3) 從目前格向箭頭方向前進一格,對此格進行(2)
(4) 從(m,n)到(0,0)的不同路徑中,斜線箭頭"\"相對應的格的元素構成最長公共子序列.如圖bcbd、bcdb、badb.
題目:求兩個字元串的最長公共子序列的長度.
輸入:第一行字元串s1,第二行字元串 s2 (1<=字元串長度<=1000).輸出:數字m,為最長公共子序列長度.測試用例如下:
輸入
bdcaba
abcbdab
輸出
4
abklmnabcdi
abcdefghijklmnopqrstuvwxyz
6
輸入:輸入檔案中的第1行是一個正整數t(0<t<=10),表示有t組測試資料.接下來是每組測試資料的描述,每組測試資料有3行.測試資料的第1行有2個正整數m、n,中間用一個空格隔開(0<m，n<50);第2、3行是長度分别為m、n的2個序列x和y,每個序列的元素間用一個空格隔開.序列中每個元素由字母、數字等構成.輸入直到檔案結束
輸出:對輸入中的每組測試資料,先輸出case #表示第幾組資料,在輸出最長公共子序列,輸出所有的最長公共子序列,并輸出動态規劃表格c表和b表.(測試用例見結果圖)
這裡涉及到一個新的問題：就是使用上面所叙述的填充表格來實作動态規劃,其中c[m,n]記錄的是目前序列的最長子序列長度;還需要引用一個吧b[m,n]表來尋找所有最長公共子序列,并把結果存入到result[]數組中.其中最重要的代碼就是兩個實作的函數,如下:
第一個lsclength函數是求最長公共子序列長度的函數,并在該函數中填充c[m][n]和b[m][n].
第二個displaylsc函數是通過b[m][n]遞歸計算所有最長公共子序列,并存儲至result數組中.
最後輸出的結果如下圖所示:
希望該文章對大家有所幫組,同時該文章參考了王曉東的《計算機算法設計與分析》,并引用了自己學校的ppt動态規劃内容.同時感謝夢醒潇湘love部落客的文章,希望大家也可以去見解該文章.
<a target="_blank" href="http://blog.chinaunix.net/uid-26548237-id-3374211.html">http://blog.chinaunix.net/uid-26548237-id-3374211.html</a>
文章主要是對自己以前學過的知識的鞏固以記錄,如果有錯誤或不足之處,希望大家海涵.