最长公共子序列LCS

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 int main()
 6 {
 7     int dp[100][100];
 8     char ch1[100],ch2[100];
 9     int i,j;
10     while(cin>>ch1>>ch2)
11     {
12         int len1=strlen(ch1),len2=strlen(ch2);
13         for(i=0;i<len1;i++)
14             for(j=0;j<len2;j++)
15             {
16                 if(ch1[i]==ch2[j])
17                     dp[i+1][j+1]=dp[i][j]+1;
18                 else
19                     dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
20             }
21             cout<<dp[len1][len2]<<endl;
22     }
23 }