模板：LCS（最长公共子序列）

 1 #include <cstring>
 2 
 3 #define max(a,b) ((a) > (b) ? (a) : (b))
 4 
 5 int same(char ch1,char ch2)
 6 {
 7     if(ch1 == ch2) return 1;
 8     else return 0;
 9 }
10 
11 int LCS(char *str1,char *str2,int len1,int len2)
12 {
13     int i,j;
14 
15     if(len1 < len2) {char *str3 = str1;str1 = str2;str2 = str3;}
16 
17     int **dp = new int*[2];
18     for(i = 0; i < 2; ++i) dp[i] = new int[len2 + 1];
19     memset(dp[0],0,sizeof(int) * (len2 + 1));
20     dp[1][0] = 0;
21 
22     
23     for(i = 1; i <= len1; ++i)
24     {
25         for(j = 1; j <= len2; ++j)
26         {
27             dp[i % 2][j] = max(dp[(i - 1) % 2][j],max(dp[i % 2][j - 1],dp[(i - 1) % 2][j - 1] + same(str1[i - 1],str2[j - 1])));
28             //cout<<"dp[" << i << "][" << j << "]=" << dp[i % 2][j] << endl;
29         }
30     }
31     int max = dp[len1 % 2][len2];
32 
33     for(i = 0; i < 2; ++i) delete [] dp[i];
34     delete [] dp;
35 
36     return max;
37 }