动态规划之最长公共子序列LCS

        Q：有一天，你突然对“少年科学院”感兴趣，在百度百科上搜索，因为在百度百科上没有这个词条，于是就d出与“少年科学院”相似有关的词条，排除大众浏览量与字典序的话，那么，它是如何排序的呢???

        最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题。一个数列 ，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则称为已知序列的最长公共子序列

        以上为百度百科的解释，说的通俗一些，就是两个字符串，求出他们相同的子序列，求出最长的长度。

方法有许多

        1.贪心，时间复杂度是O(n³)，跑得慢

        2.DP，今天的主角

        如果用一个二维数组dp表示字符串X和Y中对应的前i，前j个字符的LCS的长度话,那我们就可以得到这两条公式。

        a,b为两个字符串

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]);

        说了那么多，来看一下模板吧，Show me the code!!!

        Q:a,b两个字符串的LCS

#include 
using namespace std;
int lena,lenb,dp[1005][1005];
string a,b;
int main()
{
    cin>>a>>b;
    lena=a.size();
    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<

abcfbc abfcab
programming contest 
abcd mnp

4
2
0

#include 
using namespace std;
string a,b;
int main()
{
    while(cin>>a>>b)
    {
    	int dp[1005][1005];
    	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<

ABCBA 

0

ABECDCBABC

3

#include 
using namespace std;
int dp[1005][1005];
string s,a;
int main()
{
    cin>>s;
    for(int i=s.size()-1;i>=0;i--)
    {
    	a+=s[i];
    }
    int lena=a.size();
    int lenb=s.size();
    for(int i=1;i<=a.size();i++)
    {
        for(int j=1;j<=s.size();j++)
        {
            if(a[i-1]==s[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<