【动态规划】求最长公共子序列

蔚落 2022-08-09 00:59 216阅读 0赞

最长公共子串和最长公共子序列的区别：

> 最长公共子串和最长公共子序列的区别为：子串是串的一个连续的部分，子序列则是从不改变序列的顺序，而从序列中去掉任意的元素而获得新的序列；也就是说，子串中字符的位置必须是连续的，子序列则可以不必连续。

**题目**：求两个字符串中的最长公共子序列。  
比如： string s1 = “ABCBDAB”; string s2 = “BDCABA”;它们的lcs是：BCBA；BCAB；BDAB。  
**解析**：典型的可以用动态规划做 的题目。首先看这个题目的动态规划递推公式：  
![这里写图片描述][20150929215420334]  
然后给出这个解的二维数组创建过程：  
![这里写图片描述][20150929215527660]  
要理解这个图的意思，最好按照上面公式自己推理一遍，比看冗长的文字来的深刻的多。

简单说下我的思路然后给出代码：首先要求出动态规划中二维数组的初始条件值，dp\[i\]\[0\]和dp\[0\]\[j\]的初始值，很显然都是0。然后根据初始值可以递归出后面的所有值，最后一个值代表最大长度。说下dp\[i\]\[j\]的意思，s1的前i个字符与s2的前j个字符的最长公共子序列的长度。  
对照公式：  
如果s1\[i\] == s2\[j\]： 说明s1的前i个字符与s2的前j个字符的最长公共子序列的长度等于s1\[i-1\] 和s2\[j-1\]的LCS+1。  
如果：s1\[i\] ！= s2\[j\]：说明s1的前i个字符与s2的前j个字符的最长公共子序列的长度等于s1\[i-1\]和s2\[j\]或s1\[i\]和s2\[j-1\]的最大值。

代码实现：

char result[100];
    void display_lcs(int i, int j, string& s1, int *b,int current_len,int lcs_max_len,int row,int col)
    {
        if (i==0 || j==0)   //终止条件  
        {
            for (int k=0;k<lcs_max_len;k++)
            {
                cout << result[k];
            }
            cout << endl;
            return;
        }
        if (*(b +(i)*col + (j)) == 4)
        {
            current_len--;
            result[current_len] = s1[i-1];
            display_lcs(i-1, j-1, s1, b,current_len,lcs_max_len,row ,col);
        }
        else
        {
            if (*(b +(i)*col + (j)) == 1)
            {
                display_lcs(i-1, j, s1, b,current_len,lcs_max_len,row ,col);
            }
            else if (*(b +(i)*col + (j)) == 2)
            {
                display_lcs(i, j-1, s1, b,current_len,lcs_max_len,row ,col);
            }
            else
            {
                display_lcs(i-1, j, s1, b,current_len,lcs_max_len,row ,col);
                display_lcs(i, j-1, s1, b,current_len,lcs_max_len,row ,col);
            }
        }
    }
    void lcd_length(string& s1,string& s2)
    {
        int len1,len2;  int i,j;
        int col,row;
        len1 = s1.length();
        len2 = s2.length();
        row=len1+1;col = len2+1;
        int* tag = (int*)malloc(sizeof(int)*col*row);   //1取左值，2取上值，3左右相等(任取),4取斜上角值,。
        int* dp = (int*)malloc(sizeof(int)*col*row);    //len1行，len2列:二维数组保存动态规划中的最优值。
    #define dp(i,j) *(dp +(i)*col + (j))
    #define tag(i,j) *(tag +(i)*col + (j))
        for (i = 0;i<=len1;i++) //初始化动归 tag[i,j] = 0  where i=0或j=0
            dp(i,0) = 0;
        for (j = 0;j<=len2;j++) //初始化动归 tag[i,j] = 0  where i=0或j=0
            dp(0,j) = 0;
        //寻找tag[i,j] where i>0或j>0
        for (i=1;i<=len1;i++)
        {
            for (j=1;j<=len2;j++)
            {
                if (s1[i-1] == s2[j-1]) //s1行方向，s2列方向
                {
                    dp(i,j) = dp((i-1),(j-1)) + 1;
                    tag(i,j) = 4;
                }
                else
                {
                    if (dp(i-1,j) > dp(i,j-1))
                    {
                        dp(i,j) = dp(i-1,j);
                        tag(i,j) = 1;
                    }
                    else if (dp(i-1,j) < dp(i,j-1))
                    {
                        dp(i,j) = dp(i,j-1);
                        tag(i,j) = 2;
                    }
                    else
                    {
                        dp(i,j) = dp(i,j-1);
                        tag(i,j) = 3;
                    }
                }
            }
        }   //二维数组创建完毕，最长子串的长度就是dp(len1,len2)
    //下面输出创建的二维数组，并输出最长子串
        cout << "最长子串长度：" << dp(len1,len2) << endl; 
        cout << "计算最优值效果图如下所示：" << endl;
        for (i=1;i<=len1;i++)
        {
            for (j=1;j<=len2;j++)
            {
                cout << dp(i,j) << " ";
            }
            cout << endl;
        }
        //显示最长子串
        display_lcs(len1, len2, s1, tag,dp(len1,len2),dp(len1,len2),row ,col);
    #undef tag
    #undef dp
    }

[20150929215420334]: /images/20220731/850172a2fe0242399ff1f3a8c78ae0dd.png
[20150929215527660]: /images/20220731/26032d7d14f64e3dac87abeea21a7184.png