Common Subsequence
题意&分析：
对于给定的两个字符串，求最长公共子序列。直接用LCS算法，一个DP。
代码如下：
#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define TEST cout<<"stop here"<<endl using namespace std; typedef long long ll; const ll mod = 1e9 + 7; int dp[1010][1010]; int main(){ std::ios::sync_with_stdio(false); std::cin.tie(0); string s1,s2; while(cin>> s1 >> s2){ memset(dp,0,sizeof(0)); int len1 = s1.size(); int len2 = s2.size();//cout<<len1<<" "<< len2<<endl; for(int i=1;s1[i-1];i++){ for(int j=1;s2[j-1];j++){ if(s1[i-1] == s2[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[len1][len2] <<endl; } return 0; }参考资料：
奇妙的LCS算法妙解 传送门
