若有a，b两个字符串，dp[i][j]表示a字符串前i个和b的前j个字符的最长公共子序列，由此可以推出若a[i-1]=b[i-1],则dp[i][j]=dp[i-1][j-1]+1;否则dp[i][j]=max(dp[i-1][j],dp[i][j-1])

 1 #include<iostream>
 2 #include<string.h>
 3 #include<string>
 4 #include<sstream>
 5 #include<vector>
 6 #include<deque>
 7 #include<map>
 8 #include<algorithm>
 9 #include<iomanip>
10 #include<math.h>
11 #include<set>
12 using namespace std;
13 
14 typedef long long ll;
15 typedef unsigned long long ull;
16 
17 
18 int main()
19 {
20     string me, she;
21     int dp[1005][1005];
22     while (cin >> me>>she)
23     {
24         int L1 = me.size();
25         int L2 = she.size();
26         memset(dp, 0, sizeof(dp));
27         for (int i = 1; i <= L1; i++)
28         {
29             for (int j = 1; j <= L2; j++)
30             {
31                 if (me[i - 1] == she[j - 1])
32                     dp[i][j] = dp[i - 1][j - 1] + 1;
33                 else
34                 {
35                     dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
36                 }
37             }
38         }
39         cout << dp[L1][L2] << endl;
40     }
41     return 0;
42 }