最长公共子序列

最长公共子序列:给定两个序列S1和S2，求二者公共子序列S3的最长的长度。

有了前面的基础，可以发现这个问题仍然可以按照序列的长度来划分状态，也就是S1的前i个字符和S2的前j个字符的最长公共子序列长度，记为lcs[i[j]。

如果S1的第i项，和S2的第j项相同，那么S1[i]与S2[j]作为公共子序列的末尾，则

lcs[i][j]= lcs[i-1][j-1]+1

也可以不让S1[i]与S2[j]作为公共子序列的末尾，则

lcs[i][i] = max(lcs[i][j-1],Ics[i-1][i])

不难证明：

max(lcs[i][j-1],Ics[i-1][j])< Ics[i-1][j-1]+1

那么转移方程是:

举一个例子，两个序列 S1​ = abcfbc和S2​ = abfcab，根据转移方程可以得出 lcs[i][j]

实现代码：

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int dp[110][110];
int main() 
{
    string a, b;
    memset(dp, 0, sizeof(dp));
    cin >> a >> b;
    int lena = a.size();
    int lenb = b.size();
    for (int i = 1; i <= lena; i++)
    {
        for (int j = 1; j <= lenb; j++)
        {
            if (a[i - 1] == b[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    cout << dp[lena][lenb] << endl;
    return 0;
}