自学内容网 自学内容网
自学内容网 > 正文

[动态规划]最长公共子序列

🕗 发布于 2024-11-14 02:05 动态规划  算法  

题目：

        若给定序列X={x1,x2,…,xm}，则另一序列Y={y1,y2,…,yk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：yj=xij。例如，序列Y={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。

        给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

        最长公共子序列（LCS）采用动态规划算法的模板如下：

//最长公共子序列长度
void LCSLength(char x[],char y[],int m,int n){
    for(int i = 0;i <= m;i++){  //当y序列为空时 c[i][0]为0
        c[i][0] = 0;
    }
    for(int j = 0;j <= n;j++){  //当x序列为空时 c[0][j]为0
        c[0][j] = 0;
    }

    for(int i = 1;i <= m;i++){
        for(int j = 1;j <= n;j++){
            if(x[i] == y[j]){  //两个序列当前元素相同  取斜上方的值+1
                c[i][j] = c[i-1][j-1] + 1;
            }else if(c[i][j-1] >= c[i-1][j]){  //不相同 比较上方和左方值的大小
                c[i][j] = c[i][j-1];
            }else if(c[i][j-1] < c[i-1][j]){
                c[i][j] = c[i-1][j];
            }
        }
    }
}

//最长公共子序列
void LCS(int i, int j){
    if(i == 0 || j == 0){
        return;
    }

    if(b[i][j] == 1){  // x[i] == y[j]  斜上方找下一个相同的元素
        LCS(i-1,j-1);
        cout<<x[i]<<" ";
    }else if(b[i][j] == 2){  // c[i][j-1] >= c[i-1][j] 向左找
        LCS(i,j-1);
    }else if(b[i][j] == 3){  // c[i][j-1] < c[i-1][j] 向右找
        LCS(i-1,j);
    }
}

        状态转移方程为：

  • i = 0，j = 0 说明有一个（或两个）序列为空，所以最长公共子序列长度为0；
  • x[i] = y[j] 说明此时两个序列当前元素相同，那么找到( x[i-1]，y[j-1] )的最长公共子序列长度即可，所以 c[i][j] = c[i-1][j-1] + 1。
  • x[i] != y[j] 说明此时两个序列当前元素不相同，那么找到( x[i-1]，y[j] )或( x[i]，y[j-1] )的最长公共子序列长度即可，取较大值。所以c[i][j] = max(c[i-1][j]，c[i][j-1])。

01026e0abe3942a8be55d1183ee2669f.png

        下面给大家举一个例子，方便理解：

        假设 x 序列 的元素为{A，B，C，B，D，A，B}，y 序列的元素为{B，D，C，A，B，A}。我们可以画出对应的二维表，如下图所示。

f89446d75f2344aa92e6bd440f8501ed.png

        接下来我们开始动态规划。假设有一个序列为空时，最长公共子序列长度 c[i][j] 的值为0。（没有元素相同，所以最长公共子序列长度为0） 。

e9f70b658be74129885801672eab8799.png

        接下来双重 for 循环开始遍历剩下的所有点。在坐标（x[1]，y[4]）处，两个序列此时的元素相同，所以取斜上方的值+1。在坐标（x[1]，y[5]）处，两个序列此时的元素不相同，所以比较上方和左方值的大小，取两者中大的。

aeebe4b3d2f74bdab34834b4fac6e0f8.png

        按照上述方法，可以补全最长公共子序列长度 c[i][j]。

ed4a8f91c8bd41c9b7aba0899901b1c6.png

        以上求解的是最长公共子序列长度，接下来我们讨论最长公共子序列。 在代码中，我们已经将 c[i][j] 的来源的每一种情况都记录在了 b[i][j] 中。注意，找最长公共子序列应该从b[m][n]开始找，也就是最后一个格子。

  • 如果 b[i][j] == 1，表示 x[i] == y[j]，所以向斜上方找上一个相同的元素。
  • 如果 b[i][j] == 2，表示当前元素的 c[i][j] 是因为 c[i][j-1] >= c[i-1][j]，所以向左找上一个相同的元素。
  • 如果 b[i][j] == 3，表示当前元素的 c[i][j] 是因为 c[i][j-1] < c[i-1][j]，所以向上找上一个相同的元素。

        上面的图是根据代码的逻辑画的，但这有一个缺点，它只能找到众多可能中的一个最长公共子序列。 

        下面是一种可以找到所有可能的最长公共子序列的方法，大家可以参考。

        希望大家学有所获！


原文地址：https://blog.csdn.net/2202_75336422/article/details/143729020

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024