DP专题之LCS(Longest Common Subsequence)

 1 /*
 2     LCS(Longest Common Subsequence)裸题：
 3         状态转移方程：dp[i+1][j+1] = dp[i][j] + 1; (s[i] == t[i])
 4                         dp[i+1][j+1] = max (dp[i][j+1], dp[i+1][j]);    (s[i] != t[i])
 5 */
 6 #include <cstdio>
 7 #include <cstring>
 8 #include <iostream>
 9 #include <string>
10 #include <algorithm>
11 using namespace std;
12 
13 const int MAXN = 3e2 + 10;
14 const int INF = 0x3f3f3f3f;
15 
16 char s[MAXN];
17 char t[MAXN];
18 int dp[MAXN][MAXN];
19 
20 void LCS(int len1, int len2)
21 {
22     for (int i=0; i<len1; ++i)
23     {
24         for (int j=0; j<len2; ++j)
25         {
26             if (s[i] == t[j])
27             {
28                 dp[i+1][j+1] = dp[i][j] + 1;
29             }
30             else
31             {
32                 dp[i+1][j+1] = max (dp[i][j+1], dp[i+1][j]);
33             }
34         }
35     }
36 }
37 
38 int main(void)      //POJ 1458 Common Subsequence
39 {
40     #ifndef ONLINE_JUDGE
41     freopen ("LCS.in", "r", stdin);
42     #endif
43 
44     while (~scanf ("%s%s", &s, &t))
45     {
46         memset (dp, 0, sizeof (dp));
47         int len1 = strlen (s);
48         int len2 = strlen (t);
49 
50         LCS (len1, len2);
51         printf ("%d\n", dp[len1][len2]);
52     }
53 
54     return 0;
55 }