最长公共子序列问题2080

r囧r小猫 2022-06-09 01:44 83阅读 0赞

**集训的时候老师讲的时候就不是很懂，几天没做，更是忘得一干二净了，从网上找了一份大神的笔记，顿时清晰了好多。**

**[点击打开链接][Link 1]**

**动态规划法（看大神的笔记对动态规划也有了新的认识）**

经常会遇到复杂问题不能简单地分解成几个子问题，而会分解出一系列的子问题。简单地采用把大问题分解成子问题，并综合子问题的解导出大问题的解的方法，问题求解耗时会按问题规模呈幂级数增加。

**为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。**

【问题】 求两字符序列的最长公共字符子序列

问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列<i0，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。

考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”为它们的最长公共子序列。不难证明有以下性质：

（1） 如果am-1=bn-1，则zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一个最长公共子序列；

（2） 如果am-1!=bn-1，则若zk-1!=am-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列；

（3） 如果am-1!=bn-1，则若zk-1!=bn-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列。

这样，在找A和B的公共子序列时，如有am-1=bn-1，则进一步解决一个子问题，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一个最长公共子序列；如果am-1!=bn-1，则要解决两个子问题，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列，再取两者中较长者作为A和B的最长公共子序列。

求解：

引进一个二维数组c\[\]\[\]，用c\[i\]\[j\]记录X\[i\]与Y\[j\] 的LCS 的长度，，b\[i\]\[j\]记录c\[i\]\[j\]是通过哪一个子问题的值求得的，以决定搜索的方向。我们是自底向上进行递推计算，那么在计算c\[i,j\]之前，c\[i-1\]\[j-1\]，c\[i-1\]\[j\]与c\[i\]\[j-1\]均已计算出来。此时我们根据X\[i\] = Y\[j\]还是X\[i\] != Y\[j\]，就可以计算出c\[i\]\[j\]。

问题的递归式写成：

![recursive formula][]

回溯输出最长公共子序列过程：

![flow][]

以上都是大神的笔记，自己总结的还是弱爆了，就不改了。嘿嘿。

### 最长公共子序列问题 ###

Time Limit: 1000MS Memory Limit: 65536KB

[Submit][] [Statistic][]

#### Problem Description ####

给定两个序列X=

#### Input ####

输入数据有多组，每组有两行 ，每行为一个长度不超过500的字符串（输入全是大写英文字母（A,Z）），表示序列X和Y。

#### Output ####

每组输出一行，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出0。

#### Example Input ####

ABCBDAB
    BDCABA

#### Example Output ####

代码：

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int main()
    {
    char x[505],y[505];
    while(gets(x)&&gets(y))
    {
        int m,n;
        m = strlen(x);
        n = strlen(y);
        int c[505][505],i,j;
        for(i = 0;i<=m;i++)
            c[i][0] = 0;
        for(i =0;i<=n;i++)
            c[0][i] = 0;
       for(i =1;i<=m;i++)
        for(j=1;j<=n;j++)
       {
           if(x[i-1]==y[j-1])
            c[i][j] = c[i-1][j-1] + 1;
           else
           {
               if(c[i-1][j]>c[i][j-1])
                c[i][j] = c[i-1][j];
               else
                c[i][j] = c[i][j-1];
           }
       }
        printf("%d\n",c[m][n]);
    }
    
    
        return 0;
    }
     
    留给自己的作业 ：找时间写一个输出最长子序列的程序：

[Link 1]: http://blog.csdn.net/yysdsyl/article/details/4226630/
[recursive formula]: /images/20220609/0939bf390b05480cbb27a7eb6ba58756.png
[flow]: /images/20220609/462602cc988d428e8c429730ddecf0a8.png
[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2187/pid/2080.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2187/pid/2080.html