动态规划之最长公共子序列求解

简介: 关于最长公共子序列(LCS) 最长公共子序列和最长公共子串是有区别的,之前我一直把它们混淆。 最长公共子串举例:假设S1={A,D,C,B,E,X,Q},S2={H,P,D,C,B,E,M,L}那么它们的最长公共子串就是{D,C,B,E}。

关于最长公共子序列(LCS)

最长公共子序列和最长公共子串是有区别的,之前我一直把它们混淆。

  1. 最长公共子串举例:假设S1={A,D,C,B,E,X,Q},S2={H,P,D,C,B,E,M,L}
    那么它们的最长公共子串就是{D,C,B,E}。这是我通常理解的东西。

最长公共子序列。

  1. 最长公共子序列举例:假设S1={A,B,C,A,D,A,B},S2={B,A,C,D,B,A},那么它们的LCS就是{B,A,D,B}。

求解最长公共子序列

这是一个动态规划问题。如何求解最长公共子序列(以下用LCS代替)呢?我们假设已经知道Z={z1,z2,...zk}是X={x1,x2,...,xm}和Y={y1,y2,...,yn}的LCS,那么可以分以下三种情况讨论(具体每种情况证明不再累述):

  1. xm=yn=zk:那么Zk-1是Xm-1和Yn-1的LCS。
  2. xm≠yn,yn≠zk:我们可以把yn去掉,那么Zk是Xm和Yn-1的LCS。
  3. xm≠yn,xm≠zk:我们可以把xm去掉,那么Zk是Xm-1和Yn的LCS。

基于以上情况,我们可以得到LCS递归式。我们假设ci表示Xi和Yi的LCS长度,那么:

  • ci=0(i=0或j=0);
  • ci=c[i-1]c[j-1]+1(i,j>0且xi=yi);
  • ci=max{ci-1,c[i],[j-1]};(i,j>0且xi≠yi)。

这样我们就可以得到LCS的长度。如何得到具体内容是什么呢?我们可以借用一个辅助数组bi,这个数组用来记录ci的来源,分别有如下情况:

  • ci=ci-1+1,则bi=1;
  • ci=ci,则bi=2;
  • ci=ci-1,则bi=3。

这样就可以根据bm反向追踪LCS,当bi=1,输出xi;当bi=2,追踪ci;当bi=3,追踪ci-1,直到i=0或j=0停止。

算法设计

(1)初始化。初始化c[][]第1行和第1列为0。
(2)开始操作。具体是将s1[i]分别与s2[j-1](j=1,2,...,len2)进行比较,若字符相等ci=左上角数值+1,且bi=1;若不相等,则ci等于左侧或者上侧重最大的一个数值,若左侧和上侧相等,则取左侧,且bi=2或3(当取左侧为2,取上侧为3)。最后的c[][]和b[][]如下所示:
下表是c[][]:

0 1 2 3 4 5 6
0 0 0 0 0 0 0
A 0 0 1 1 1 1 1
B 0 1 1 1 1 2 2
C 0 1 1 2 2 2 2
A 0 1 2 2 2 2 3
D 0 1 2 2 3 3 3
A 0 1 2 2 3 3 4
B 0 1 2 2 3 4 4

下表是b[][]:

0 1 2 3 4 5 6
0 0 0 0 0 0 0
1 0 2 1 2 2 2 1
2 0 1 2 2 2 1 2
3 0 3 2 1 2 2 2
4 0 3 1 2 2 2 1
5 0 3 3 2 1 2 2
6 0 3 1 2 3 2 1
7 0 1 3 2 3 1 2

根据c[][]可以得出,LCS的长度为4(也就是c[][]最后一个值)。然后开始判断内容是什么,这是要根据b[][]来。
首先,b7=2,向左找b7=1,所以向左上角找b6,得到字母为s1[6]=[B];
b6=3,向上找b5=1,向左上角找b4,得到字母s1[4]=[D];
b4=2,向左找b4[1],得到字母s1[3]=[A];
b3=3,向上找b2=1,向左上角找b1,得到字母s1[1]=[B].
由于b1=0,所以算法停止,返回结果为“BADB”。

代码演示

void LCSL()
{
    int i, j;
    for(i=1;i<len1;i++)
        for (j = 1; j < len2; j++)
        {
            if (s1[i - 1] == s2[j - 1])
            {
                c[i][j] = c[i - 1][j - 1] + 1;
                b[i][j] = 1;
            }
            else
            {
                if (c[i][j - 1] >= c[i - 1][j])
                {
                    c[i][j] = c[i][j - 1];
                    b[i][j] = 2;
                }
                else
                {
                    c[i][j] = c[i - 1][j];
                    b[i][j] = 3;
                }
            }
        }
}

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, j - 1);
    else
        print(i - 1, j);
}
相关文章
|
2月前
|
算法
动态规划算法学习二:最长公共子序列
这篇文章介绍了如何使用动态规划算法解决最长公共子序列(LCS)问题,包括问题描述、最优子结构性质、状态表示、状态递归方程、计算最优值的方法,以及具体的代码实现。
158 0
动态规划算法学习二:最长公共子序列
|
7月前
|
人工智能
最长公共子序列(经典动态规划问题)
最长公共子序列(经典动态规划问题)
|
算法 JavaScript Go
【动态规划】最长递增子序列
【动态规划】最长递增子序列
|
算法
【学会动态规划】 最长递增子序列(26)
【学会动态规划】 最长递增子序列(26)
47 0
深入理解动态规划算法 - 最长公共子序列
深入理解动态规划算法 - 最长公共子序列
79 0
深入理解动态规划算法 | 最长公共子序列LCS
深入理解动态规划算法 | 最长公共子序列LCS
130 0
动态规划-公共子序列问题
前言 前面我们学习了动态规划的背包类型问题,其中涉及01背包,完全背包,多重背包。现在我们来继续学习动态规划的公共子序列问题。
|
算法 关系型数据库 MySQL
浅谈最长公共子序列引发的经典动态规划问题
这篇文章通过一道经典例题:最长公共子序列,给大家讲讲动态规划,并且给出一道LeetCode周赛动态规划题作为练手并讲解,相信看完文章之后,你会对动态规划有更深的理解。
124 0
浅谈最长公共子序列引发的经典动态规划问题
LeetCode 动态规划之最长公共子序列
LeetCode 动态规划之最长公共子序列
141 0
LeetCode 动态规划之最长公共子序列