Description
Input
Output
Sample Input
abcfbc abfcab programming contest abcd mnp
Sample Output
4 2 0
题解：给你两个字符串，找到他们最长的公共子序列。这个题做过很多次，虽然加了点东西，还是没有写对，还是对LCS理解不够。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; char a[1100],b[1100]; int dp[1100][1100]; int main() { while(scanf("%s %s",a,b)!=EOF) { int x=strlen(a); int y=strlen(b); for(int i=1;i<=x;i++) { for(int j=1;j<=y;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[x][y]<<endl; } return 0; }
原文：http://www.cnblogs.com/hfc-xx/p/4732715.html