sicily LCS

直接用递归做了一下，超时了，可能要再加上记忆化搜索？不会...

然后再用动态规划就过了...

http://soj.sysu.edu.cn/show_problem.php?pid=1002&cid=1762

 1 //直接递归，tle
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 char s1[1001];
 9 char s2[1001];
10 
11 int LCS(char s1[], char s2[], int len1, int len2)
12 {
13     if(len1 == 0 || len2 == 0)
14         return 0;
15     if(s1[len1-1] == s2[len2-1])
16         return 1+LCS(s1, s2, len1-1, len2-1);
17     else
18         return max(LCS(s1, s2, len1-1, len2), LCS(s1, s2, len1, len2-1));
19 }
20 
21 int main()
22 {
23     while(cin >> s1 >> s2)
24     {
25         int len1 = strlen(s1);
26         int len2 = strlen(s2);
27         cout << LCS(s1, s2, len1, len2) << endl;
28     }
29     return 0;
30 }

 1 //动规，思路是一样的
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 
 6 using namespace std;
 7 
 8 char s1[1001];
 9 char s2[1001];
10 int dp[1001][1001];
11 
12 int LCS(char s1[], char s2[])
13 {
14     int len1 = strlen(s1);
15     int len2 = strlen(s2);
16     memset(dp, 0, sizeof(dp));
17     
18     for(int i=1; i<=len1; i++)
19     {
20         for(int j=1; j<=len2; j++)
21         {
22             if(s1[i-1] == s2[j-1])
23                 dp[i][j] = dp[i-1][j-1] + 1;
24             else
25                 dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
26         }
27     }
28     return dp[len1][len2];
29 }
30 
31 int main()
32 {
33     while(cin >> s1 >> s2)
34     {
35         cout << LCS(s1, s2) << endl;
36     }
37     return 0;
38 }