动态规划解最长公共子序列(LCS)

「爱情、让人受尽委屈。」 2023-06-27 03:42 7阅读 0赞

本次博客，直接简述核心动态规划部分，需要先对动态规划以及什么是最长公共子序列有简单了解，可以参考下博客，

最长公共子序列 (LCS) 详解+例题模板（全）  
[https://blog.csdn.net/lxt\_Lucia/article/details/81209962][https_blog.csdn.net_lxt_Lucia_article_details_81209962]  
动态规划解最长公共子序列(LCS)(附详细填表过程)  
[https://blog.csdn.net/weixin\_40673608/article/details/84262695][https_blog.csdn.net_weixin_40673608_article_details_84262695]

递归关系：  
![在这里插入图片描述][20200102202616253.png]  
根据递归关系

如果 x i = y i x\_i = y\_i xi=yi,则会有 C \[ i − 1 , j − 1 \] + 1 C\[i-1,j-1\]+1 C\[i−1,j−1\]\+1  
如果 x i ！ = y i x\_i ！= y\_i xi！=yi，则会有 m a x C \[ i , j − 1 \] , C \[ i − 1 , j \] max\{C\[i,j-1\],C\[i-1,j\]\} maxC\[i,j−1\],C\[i−1,j\]

假如我们有两个序列，分别为ABCDE和WBFCE，我们可以分析过程如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70]  
详细代码是借鉴的网上的，自己加了注释。

/*
    思路：
    
    此题的切入点就是动态规划，
    
    通过递归来确定哪些字符是最长公共子序列中的字符，
    mat[i][j] 表示第一个序列的前i个字符和第二个序列的前j个字符的公共子序列，动态转移方程为：
    
    dp[i][j] = max(dp[i-1][j], dp[i][j-1],dp[i-1][j-1] + (A[i]==B[j] ? 1 : 0))，表示在这三种状态中取到最大值，
    
    （1）第一种状态表示不录入第一个序列的第i个字符时的最长公共子序列，
    
    （2）第二种状态表示不录入第二个序列的第j个字符时的最长公共子序列，
    
    （3）第三种状态表示第一个序列的前i-1个字符与第二个序列前j-1个字符的公共子序列加上最后一个字符的录入状态，
    如果最后的一个字符相等则录入状态为1，否则为0。
    */
    #include<queue>
    #include<cmath>
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    #define INF 0x3f3f3f3f
     
    using namespace std;
     
    char a[1001], b[1001];
    int dp[1001][1001], len1, len2;
    //填完表格 ，递归关系的应用
    //dp[i][j] = max(dp[i-1][j], dp[i][j-1],dp[i-1][j-1] + (A[i]==B[j] ? 1 : 0)) 
    void lcs(int i, int j)
    {
        for(i=1; i<=len1; i++)
        {
            for(j=1; j<=len2; j++)
            {
            	//如果相等，则将 dp[i-1][j-1] + 1
                if(a[i-1] == b[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                //不想等，取最大的 
                else if(dp[i-1][j] > dp[i][j-1])
                    dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = dp[i][j-1];
            }
        }
    }
     
    void llcs()
    {
        int i, j, z = 0;
        char c[1001];
        memset(c, 0, sizeof(c));
        i = len1, j = len2;
        //递归关系的应用 
        while(i!=0 && j!=0)
        {
        	//逆过程回去，如果相等，则加入数组，同时横纵坐标均减一 
            if(a[i-1] == b[j-1])
            {
                c[z++] = a[--i];
                j--;
            }
            //如果不相等，判断当前位置左方和上方的数谁大，数大的位置也就是当时这个数 
            else if(dp[i-1][j] < dp[i][j-1])
                j--;
            else if(dp[i][j-1] <= dp[i-1][j])
                i--;
        }
        for(i=z-1; i>=0; i--)
            printf("%c", c[i]);
        printf("\n");
     
    }
     
    int main()
    {
        while(~scanf(" %s", a))
        {
            scanf(" %s", b);
            memset(dp, 0, sizeof(dp));
            len1 = strlen(a);
            len2 = strlen(b);
            lcs(len1, len2);
            llcs();
        }
        return 0;
    }

[https_blog.csdn.net_lxt_Lucia_article_details_81209962]: https://blog.csdn.net/lxt_Lucia/article/details/81209962
[https_blog.csdn.net_weixin_40673608_article_details_84262695]: https://blog.csdn.net/weixin_40673608/article/details/84262695
[20200102202616253.png]: https://img-blog.csdnimg.cn/20200102202616253.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200102202729114.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU=,size_16,color_FFFFFF,t_70