本文共 2908 字，大约阅读时间需要 9 分钟。

运行结果如图：

算法设计

最长公共子序列问题满足动态规划的最优子结构性质，可以自底向上逐步得到最优解。

（1）确定合适的数据结构 采用二维数组c[][]来记录最长公共子序列的长度，二维数组b[][]来记录最长公共子序列的长度的来源，以便算法结束时倒推求解得到该最长公共子序列。 （2）初始化 输入两个字符串s1、s2，初始化c[][]第一行第一列元素为0。 （3）循环阶段 i = 1：s1[0]与s2[j-1]比较，j=1，2，3，…，len2。 如果s1[0]=s2[j-1]，c[i][j] = c[i-1][j-1]+1；并记录最优策略来源b[i][j]=1； 如果s1[0] ≠s2[j-1]，则公共子序列的长度为c[i][j-1]和c[i-1][j]中的最大值，如果c[i][j-1]c[i-1][j]，则c[i][j]=c[i][j-1]，最优策略来源b[i][j]=2；否则c[i][j]= c[i-1][j]，最优策略来源b[i][j]=3。 i = 2：s1[1]与s2[j-1]比较，j=1，2，3，…，len2。 以此类推，直到i > len1时，算法结束，这时c[len1][len2]就是最长公共序列的长度。 （4）构造最优解 根据最优决策信息数组b[][]递归构造最优解，即输出最长公共子序列。因为我们在求最长公共子序列长度c[i][j]的过程中，用b[i][j]记录了c[i][j]的来源，那么就可以根据b[i][j]数组倒推最优解。 如果b[i][j]=1，说明s1[i-1]=s2[j-1]，那么就可以递归求解print(i-1, j-1)；然后输出s1[i-1]。 注意：如果先输出，后递归求解print(i-1,j-1)，则输出的结果是倒序。 如果b[i][j]=2，说明s1[i-1]≠s2[j-1]且最优解来源于c[i][j]=c[i][j-1]，递归求解print(i, j-1)。 如果b[i][j]=3，说明s1[i-1]≠s2[j-1]且最优解来源于c[i][j]=c[i-1][j]，递归求解print(i-1, j)。当i0 || j0时，递归结束。

图解

以字符串s1=“ABCADAB”，s2=“BACDBA”为例。

（1）初始化 len1=7，len2=6，初始化c[][]第一行、第一列元素为0，如图4-7所示。 图 4-7

2）i=1：s1[0]与s2[j-1]比较，j=1，2，3，…，len2。即“A”与“BACDBA”分别比较一次。 如果字符相等，c[i][j]取左上角数值加1，记录最优值来源b[i][j]=1。 如果字符不等，取左侧和上面数值中的最大值。如果左侧和上面数值相等，默认取左侧数值。如果c[i][j]的值来源于左侧b[i][j]=2，来源于上面b[i][j]=3。 j=1：A≠B，左侧=上面，取左侧数值，c[1][1]= 0，最优策略来源b[1][1]=2，如图4-8所示。 图4-8　最长公共子序列求解过程 j=2：A=A，则取左上角数值加1，c[1][2]= c[0][1]+1=2，最优策略来源b[1][2] =1，如图4-9所示。 图4-9　最长公共子序列求解过程 j=3：A≠C，左侧上面，取左侧数值，c[1][3]= 1，最优策略来源b[1][3] =2，如图4-10所示。

图4-9

图4-10

最后得到的b数组：

完整代码：

int len1, len2;const int n = 1002;int b[n][n];//b[i][j]表示c[i][j]的来源，用于输出最长公共子序列 为1时说明s1[i-1]=s2[j-1] 则可以递归函数print再输出s1[i-1]//b[i][j]为2时说明s1[i-1]不等于s2[j-1] 最优解来源于c[i][j]=c[i][j-1] 递归输出print(i,j-1)//为3时说明1[i-1]不等于s2[j-1] 最优解来源于c[i][j]=c[i-1][j] 递归输出print(i-1,j) i或者j为0时递归结束int c[n][n];//c[len1][len2]表示最长公共子序列的长度char s1[n], s2[n];void LCSL() {
       for (int i = 1; i <= len1; i++)         for (int j = 1; j <= len2; j++) {
               if (s1[i - 1] == s2[j - 1]) {
                   b[i][j] = 1;                c[i][j] = c[i - 1][j - 1] + 1;            }            else if (c[i - 1][j] >= c[i][j - 1]) {
                   b[i][j] = 2;                c[i][j] = c[i - 1][j];            }            else {
                   b[i][j] = 3;                c[i][j] = c[i][j - 1];            }        }    }        void print(int i, int j) {
               if (i == 0 || j == 0) return;            if (b[i][j] == 1)            {
                   print(i - 1, j - 1);                cout << s1[i - 1];            }            else if (b[i][j] == 2) {
                   print(i - 1, j);            }            else                print(i, j - 1);        }int main(){
          cout << "input s1 and s2";    cin >> s1;    cout << "s2:";    cin >> s2;    len1 = strlen(s1);    len2 = strlen(s2);    for (int i = 0; i < len1; i++) {
           for (int j = 0; j < len2; j++) {
               c[0][j] = 0;            c[i][0] = 0;        }    }    LCSL();    print(len1, len2);}

摘录自书籍《趣学算法》动态规划章节

转载地址：http://itten.baihongyu.com/