最长公共子序列（LCS）（动态规划，递归）

 1）从前往后递推：

• 状态设计：dp[i][j]表示两个序列从首位置开始，第一个序列到i-1位置，  第二个到j-1位置的最长公共子序列；
•     状态转移方程：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]);
• 边界：dp[0][j]=dp[i]=0;(i=0...len1,j=0...len2);
•     最后可根据dp[i][j]的值输出最长公共子序列的内容，当dp[i][j]== (dp[i-1][j] || dp[i][j-1]时，明显str1[i]!=str[j]；当dp[i][j]==dp[i-1][j-1]时，明显str1[i]==str2[j]，那么就把这个元素加到 str中。
•      当然，如果从前往后递推，字符的下标是从1开始的，那么状态设计可以这么表示：状态设计：dp[i][j]表示两个序列从首位置开始，第一个序列到i位置，第二个到j位置的最长公共子序列；而我下面的 程序输入的字符下标是从0开始输入的。

/**
    1)状态设计：dp[i][j]表示两个序列从首位置开始，第一个序列到i-1位置，
    第二个到j-1位置的最长公共子序列；
    状态转移方程：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]);
    边界：dp[0][j]=dp[i]=0;(i=0...len1,j=0...len2);

    最后可根据dp[i][j]的值输出最长公共子序列的内容，当dp[i][j]==
    (dp[i-1][j] || dp[i][j-1]时，明显str1[i]!=str[j]；当dp[i][j]
     ==dp[i-1][j-1]时，明显str1[i]==str2[j]，那么就把这个元素加到
     str中。

     当然，如果从前往后递推，字符的下标是从1开始的，那么状态设计
     可以这么表示：状态设计：dp[i][j]表示两个序列从首位置开始，
     第一个序列到i位置，第二个到j位置的最长公共子序列；而我下面的
     程序输入的字符下标是从0开始输入的。
*/

/**
#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]表示两个序列从首位置开始，第一个序列到i-1位置，第二个到j-1位置
    string str;             //的最长公共子序列
    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;)    //似乎又有two point 的影子
    {
        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)从后往前推；
    状态设计：dp[i][j]表示两个序列从尾位置开始，第一个序列到i位置，
    第二个到j位置的最长公共子序列；
    状态转移方程：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]);

    最后可根据dp[i][j]的值输出最长公共子序列的内容，当dp[i][j]==
    (dp[i+1][j] || dp[i][j+1]时，明显str1[i]!=str[j]；当dp[i][j]
     ==dp[i-1][j-1]时，明显str1[i]==str2[j]。

/**
    2)从后往前推；
    状态设计：dp[i][j]表示两个序列从尾位置开始，第一个序列到i位置，
    第二个到j位置的最长公共子序列；
    状态转移方程：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]);

    最后可根据dp[i][j]的值输出最长公共子序列的内容，当dp[i][j]==
    (dp[i+1][j] || dp[i][j+1]时，明显str1[i]!=str[j]；当dp[i][j]
     ==dp[i-1][j-1]时，明显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]表示两个序列从尾位置开始，第一个序列到i位置，第二个到j位置
    string str;                 //的最长公共子序列
    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;)    //似乎又有two point 的影子
    {
        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;
}
*/

递归解决：

/**
    3)递归解决
*/
#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);
    }
}