最长公共子序列----LCS

思路：

普普通通动态规划 并且判断他当前的取值是上方还是左方，并做好标记，再利用回溯，输出字符串

时间复杂度O(nlogn)

Code:

#include<iostream>
#include<cmath>
#include<string.h>
using namespace std;
const int N=3e3+5;
char a[N],b[N];
int dp[N][N],p[N][N];
int al,bl;//两个字符串的长度
void lcs()
{
    for(int i=0;i<al;i++)
    for(int j=0;j<bl;j++)
    {
        if(a[i]==b[j])//如果相等 最大值为左上方+1 
        {
            dp[i+1][j+1]=dp[i][j]+1;
            p[i+1][j+1]=1;//标记取的值是左上方的
        }
        else if(dp[i][j+1]>=dp[i+1][j])//如果上方的值大于左方的值 标记为2
        {
            dp[i+1][j+1]=dp[i][j+1];
            p[i+1][j+1]=2;
        }
        else//左方的值大于上方的值 标记为3
        {
            dp[i+1][j+1]=dp[i+1][j];
            p[i+1][j+1]=3;
         } 
    }

} 
void LCS(int i,int j)//回溯
{
    if(i==0||j==0) return ;
    if(p[i][j]==1)//p值为1  则输出左上方
    {
        LCS(i-1,j-1);
        cout<<a[i-1];
    }
    else if(p[i][j]==2)//p值为2回溯上方
    {
        LCS(i-1,j);
    }
    else //p值为3 回溯左方
    {
        LCS(i,j-1);
    }
}

int main()
{
    cin>>a>>b;
    bl=strlen(b);
    lcs();
    LCS(al,bl);
    return 0;
}