最长公共子序列问题(LCS)之动态规划法

题目描述
使用动态规划算法求解两个序列的最长公共子序列的长度。
输入
每组输入包括两行，每行包括一个字符串。
输出
两个序列的最长公共子序列的长度。
样例输入
ACBCDABD
ABDCABA
样例输出
5

ps：

100个动态规划方程

这是一个典型的求解最长公共子序列的题目，只要找到公式，问题就迎刃而解了

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int a[maxn], dp[1300][1300];
char c[110];
string s1, s2;
int lcs()
{
   
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= s1.length(); ++i)
        for (int j = 1; j <= s2.length(); ++j)
        {
   
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
}
int main()
{
   
    while (cin >> s1 >> s2)
    {
   
        lcs();
        printf("%d\n", dp[s1.length()][s2.length()]);
    }
    return 0;
}

当然也可以把函数写在主函数里面，这就要看读者的爱好了

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int a[maxn], dp[1300][1300];
char c[110];
string s1, s2;
int lcs()
{
   
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= s1.length(); ++i)
        for (int j = 1; j <= s2.length(); ++j)
        {
   
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    return dp[s1.length()][s2.length()];
}
int main()
{
   
    while (cin >> s1 >> s2)
    {
   
        printf("%d\n", lcs());
    }
    return 0;
}

接下来就上正菜了！

最长公共子序列问题(LCS)-构造LCS

题目描述
使用动态规划算法求两个序列的最长公共子序列，需构造一条最长公共子序列。
输入
每组输入包括两行，每行包括一个字符串。
输出
两个字符序列的一条最长公共子序列。（输入已确保最长公共子序列的唯一性）
样例输入
acdbxx
ccdxx
样例输出
cdxx

我们知道有时候最长公共子序列不唯一，这个题目是在保证唯一的情况下构造lcs，附上晖队的的讲解


拐角处就是匹配的位置，只要从最高层每次从拐角走到下一层…一直下到0的那一层，经过的拐角处的字
符连在一起就是一个最长公共子序列（不过是逆序的）
只要找到一种走法就行
可以从右下角开始，先向上走走到和下一层的边界，再向左走走到和下一层的边界，所在的位置便是一
个拐角
然后向左上走到下一层，继续上述操作，直到走到第0层

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
char a[maxn], b[maxn], c[maxn];
int dp[maxn][maxn];
int main()
{
   
    while (~scanf("%s %s", a + 1, b + 1)) //输入从数组下标为1开始
    {
                                        //不管怎样都要先计算出最长公共子序列的长度
        int la = strlen(a + 1);
        int lb = strlen(b + 1);
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= la; ++i)
        {
   
            for (int j = 1; j <= lb; ++j)
            {
   
                if (a[i] == b[j])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        int xx = la, yy = lb, cnt = dp[la][lb];
        c[cnt] = '\0'; //字符串的结束标志，需要自己手动补上，不然程序不知道什么时候才会截止
        while (dp[xx][yy])
        {
   
            if (dp[xx - 1][yy] >= dp[xx][yy - 1]) //如果上面那个大于左边那个
            {
   
                if (dp[xx - 1][yy] < dp[xx][yy]) //如果上面的小于长度那么就等于找到了
                {
   
                    c[--cnt] = a[xx]; //赋值
                    --yy;             //那就往左边找
                }
                else
                    --xx; //否则就往上面找
            }
            else
            {
   
                if (dp[xx][yy - 1] < dp[xx][yy])
                {
   
                    c[--cnt] = a[xx];
                    --xx;
                }
                else
                    --yy;
            }
        }
        printf("%s\n", c);
    }
}
// int xx = la, yy = lb, cnt = dp[la][lb];
// c[cnt] = '\0'; //补上字符串结束标志
// while (dp[xx][yy])
// {
   
// while (dp[xx - 1][yy] == dp[xx][yy] && xx > 1)
// { //向上走 xx>1避免出界
// --xx;
// }
// while (dp[xx][yy - 1] == dp[xx][yy] && yy > 1)
// { //向左走 yy>1避免出界
// --yy;
// }
// c[--cnt] = a[xx];
// --xx, --yy;
// }

递归代码
主要思想就是标记法+递归

#include <bits/stdc++.h>
using namespace std;
int b[1005][1005], dp[1005][1005];
char str1[1005], str2[1005];
int LCSlength()
{
   
    int ls1 = strlen(str1 + 1);
    int ls2 = strlen(str2 + 1);
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= ls1; ++i)
        for (int j = 1; j <= ls2; ++j)
        {
   
            if (str1[i] == str2[j])
            {
   
                dp[i][j] = dp[i - 1][j - 1] + 1;
                b[i][j] = 1;
            }
            else if (dp[i - 1][j] >= dp[i][j - 1])
            {
   
                dp[i][j] = dp[i - 1][j];
                b[i][j] = 2;
            }
            else
            {
   
                dp[i][j] = dp[i][j - 1];
                b[i][j] = 3;
            }
        }
    return dp[ls1][ls2];
}
void LCS(int i, int j)
{
   
    if (i == 0 || j == 0)
        return;
    if (b[i][j] == 1)
    {
   
        LCS(i - 1, j - 1);
        printf("%c", str1[i]);
    }
    else if (b[i][j] == 2)
        LCS(i - 1, j);
    else
        LCS(i, j - 1);
}
int main()
{
   
    while (~scanf("%s %s", str1 + 1, str2 + 1))
    {
   
        LCSlength();
        LCS(strlen(str1 + 1), strlen(str2 + 1));
    }
    return 0;
}