Longest common subsequence (LCS) (dynamic programming, recursive)

 1） Recursion after going ：

• State Design ：dp[i][j] Indicates that two sequences start from the first position , The first sequence goes to i-1 Location ,  The second to j-1 The longest common subsequence of positions ;
•     State transition equation ：dp[i][j]=dp[i-1][j-1]+1 (str1[i-1]==str2[j-1]);
•                                      || = max(dp[i-1][j],dp[i][j-1]) (str1[i-1]!=str2[j-1]);
• The border ：dp[0][j]=dp[i]=0;(i=0...len1,j=0...len2);
•     Finally, according to dp[i][j] Output the content of the longest common subsequence , When dp[i][j]== (dp[i-1][j] || dp[i][j-1] when , obvious str1[i]!=str[j]; When dp[i][j]==dp[i-1][j-1] when , obvious str1[i]==str2[j], Then add this element to str in .
•      Of course , If you recurs after going , The subscript of the character is from 1 At the beginning , Then state design can be expressed in this way ： State Design ：dp[i][j] Indicates that two sequences start from the first position , The first sequence goes to i Location , The second to j The longest common subsequence of positions ; And below me   The character subscript entered by the program is from 0 Start typing .

/**
    1) State Design ：dp[i][j] Indicates that two sequences start from the first position , The first sequence goes to i-1 Location ,
     The second to j-1 The longest common subsequence of positions ;
     State transition equation ：dp[i][j]=dp[i-1][j-1]+1 (str1[i-1]==str2[j-1]);
            || = max(dp[i-1][j],dp[i][j-1]) (str1[i-1]!=str2[j-1]);
     The border ：dp[0][j]=dp[i]=0;(i=0...len1,j=0...len2);

     Finally, according to dp[i][j] Output the content of the longest common subsequence , When dp[i][j]==
    (dp[i-1][j] || dp[i][j-1] when , obvious str1[i]!=str[j]; When dp[i][j]
     ==dp[i-1][j-1] when , obvious str1[i]==str2[j], Then add this element to 
     str in .

      Of course , If you recurs after going , The subscript of the character is from 1 At the beginning , So state design 
      It can be expressed in this way ： State Design ：dp[i][j] Indicates that two sequences start from the first position ,
      The first sequence goes to i Location , The second to j The longest common subsequence of positions ; And below me 
      The character subscript entered by the program is from 0 Start typing .
*/

/**
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    string str1,str2;
    cout << "input two strings:\n";
    cin >> str1 >> str2;
    int len1=str1.size(),len2=str2.size();
    int dp[len1+1][len2+1]; //dp[i][j] Indicates that two sequences start from the first position , The first sequence goes to i-1 Location , The second to j-1 Location 
    string str;             // The longest common subsequence of 
    for(int i=0;i<=len1;++i)
        dp[i][0]=0;
    for(int j=0;j<=len2;++j)
        dp[0][j]=0;
    for(int i=1;i<=len1;++i)
        for(int j=1;j<=len2;++j)
        {
            if(str1[i-1]==str2[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    for(int i=len1,j=len2;i>0&&j>0;)    // Seems to have two point  Shadow 
    {
        if(dp[i][j]==dp[i-1][j])
            --i;
        else if(dp[i][j]==dp[i][j-1])
            --j;
        else
        {
            str=str1[i-1]+str;
            --i;
            --j;
        }
    }
    cout << dp[len1][len2] << endl;
    cout << str << endl;
    cout << "Hello world!" << endl;
    return 0;
}
*/

2) Push back and forth ;
    State Design ：dp[i][j] Indicates that two sequences start from the tail position , The first sequence goes to i Location ,
    The second to j The longest common subsequence of positions ;
    State transition equation ：dp[i][j]=dp[i+1][j+1]+1 (str1[i]==str2[j]);
            || = max(dp[i+1][j],dp[i][j+1]) (str1[i]!=str2[j]);

    Finally, according to dp[i][j] Output the content of the longest common subsequence , When dp[i][j]==
    (dp[i+1][j] || dp[i][j+1] when , obvious str1[i]!=str[j]; When dp[i][j]
     ==dp[i-1][j-1] when , obvious str1[i]==str2[j].

/**
    2) Push back and forth ;
     State Design ：dp[i][j] Indicates that two sequences start from the tail position , The first sequence goes to i Location ,
     The second to j The longest common subsequence of positions ;
     State transition equation ：dp[i][j]=dp[i+1][j+1]+1 (str1[i]==str2[j]);
            || = max(dp[i+1][j],dp[i][j+1]) (str1[i]!=str2[j]);

     Finally, according to dp[i][j] Output the content of the longest common subsequence , When dp[i][j]==
    (dp[i+1][j] || dp[i][j+1] when , obvious str1[i]!=str[j]; When dp[i][j]
     ==dp[i-1][j-1] when , obvious str1[i]==str2[j].
*/

/**
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    string str1,str2;
    cout << "input two strings:\n";
    cin >> str1 >> str2;
    int len1=str1.size(),len2=str2.size();
    int dp[len1+1][len2+1]={0}; //dp[i][j] Indicates that two sequences start from the tail position , The first sequence goes to i Location , The second to j Location 
    string str;                 // The longest common subsequence of 
    for(int i=0;i<=len1;++i)
        dp[i][0]=0;
    for(int j=0;j<=len2;++j)
        dp[0][j]=0;
    for(int i=len1-1;i>=0;--i)
        for(int j=len2-1;j>=0;--j)
        {
            if(str1[i]==str2[j])
                dp[i][j]=dp[i+1][j+1]+1;
            else
                dp[i][j]=max(dp[i+1][j],dp[i][j+1]);
        }

    for(int i=0,j=0;i<len1&&j<len2;)    // Seems to have two point  Shadow 
    {
        if(dp[i][j]==dp[i+1][j])
            ++i;
        else if(dp[i][j]==dp[i][j+1])
            ++j;
        else
        {
            str+=str1[i];
            ++i;
            ++j;
        }
    }
    cout << dp[0][0] << endl;
    cout << str << endl;
    cout << "Hello world!" << endl;
    return 0;
}
*/

Recursive solution ：

/**
    3) Recursive solution 
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
string str1,str2,str;
int dp[100][100];
int lcs_len(int l1,int l2);
void lcs_str(int l1,int l2);
int main()
{
    cout << "input two strings:\n";
    cin >> str1 >> str2;
    int len1=str1.size(),len2=str2.size();
    memset(*dp,-1,sizeof dp);
    lcs_len(len1,len2);
    lcs_str(len1,len2);
    cout << dp[len1][len2] << endl;
    cout << str << endl;
    cout << "Hello world!" << endl;
    return 0;
}

int lcs_len(int l1,int l2)
{
    if(dp[l1][l2]!=-1)
        return dp[l1][l2];
    else
    {
        if(l1==0||l2==0)
            return dp[l1][l2]=0;
        if(str1[l1-1]==str2[l2-1])
            return dp[l1][l2]=lcs_len(l1-1,l2-1)+1;
        else
            return dp[l1][l2]=max(lcs_len(l1-1,l2),lcs_len(l1,l2-1));
    }
}

void lcs_str(int l1,int l2)
{
    if(l1==0||l2==0)
        return ;
    if(dp[l1][l2]==dp[l1-1][l2])
        lcs_str(l1-1,l2);
    else if(dp[l1][l2]==dp[l1][l2-1])
        lcs_str(l1,l2-1);
    else
    {
        str=str1[l1-1]+str;
        lcs_str(l1-1,l2-1);
    }
}