Common Subsequence

L - Common Subsequence

参考：ACM POJ 1458 Common Subsequence (最长公共子序列，动态规划）

思路：二维动态规划。

dp[i][j]：在截止至s1的i-1，s2的j-1位置，两个串的最长公共子序列长度。

动态规划方程：

if(s1[i]==s2[j])  dp[i+1][j+1]=dp[i][j]+1;
else  dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);

即如果s1[i]==s2[j]，则表示当前最长公子序列可加1，若不相等，则为前面的状态的dp最大值。

代码：

// Created by CAD on 2019/11/5.
#include <iostream>
#include <string>
using namespace std;

int dp[1005][1005];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s1,s2;
    while(cin>>s1>>s2)
    {
        int len1=s1.length(),len2=s2.length();
        for(int i=0;i<=len1;++i) dp[i][0]=0;
        for(int i=0;i<=len2;++i) dp[0][i]=0;
        for(int i=0;i<len1;++i)
            for(int j=0;j<len2;++j)
                if(s1[i]==s2[j]) dp[i+1][j+1]=dp[i][j]+1;
                else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
        cout<<dp[len1][len2]<<endl;
    }
    return 0;
}