动态规划法求解最长公共子序列(共8页).doc

精选优质文档-倾情为你奉上 公共子序列问题 徐康一算法设计 假设有两个序列X和Y，假设X和Y分别有m和n个元素，则建立一个二维数组C(m+1)*(n+1)，记录Xi与Yj的LCS的长度。将Ci,j分为三种情况： 若i =0 或j =0时，Ci,j=0； 若i,j0且Xi=Yj，Ci,j=Ci-1,j-1+1； 若i,j0且XiYj,Ci,j=maxCi-1,j,Ci,j-1。 再使用一个m*n的二维数组b，bi,j记录Ci,j的来向: 若Xi=Yj，则Bi,j中记入“”，记此时bi,j = 1； 若XiYj且Ci-1,j Ci,j-1，则bi,j中记入“”，记此时Bi,j = 2； 若XiYj且Ci-1,j Ci,j-1，则bi,j中记入“”，记此时Bi,j = 3； 若Xi