最长公共子序列

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 const int max_n = 1000+10;
 8 
 9 int n,m;
10 char s[max_n],t[max_n];
11 int dp[max_n][max_n];
12 
13 
14 void solve()
15 {
16     memset(dp,0,sizeof(dp));
17     for(int i=0;i<=n;++i)
18     {
19         dp[i][0]=0;
20         dp[0][i]=0;
21     }
22     for(int i=1;i<=n;++i)
23     {
24         for(int j=1;j<=m;++j)
25         {
26             if(s[i]==t[j])
27             {
28                 dp[i][j]=dp[i-1][j-1]+1;
29             }
30             else
31             {
32                 dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
33             }
34         }
35     }
36 
37     printf("%d
",dp[n][m]);
38 }
39 
40 int main()
41 {
42     scanf("%d %d",&n,&m);
43     scanf("%s",s+1);
44     scanf("%s",t+1);
45     solve();
46     return 0;
47 }
48 
49 /*
50 4 4
51 abcd
52 becd
53 */