HDU 1159 最基础的dp LCS问题

 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 const int max_n=1000;
 5 
 6 int dp[max_n][max_n];
 7 char s1[max_n],s2[max_n];
 8 
 9 int max(int a,int b)
10 {
11     return a>b?a:b;
12 }
13 
14 
15 
16 int main(void)
17 {
18     int i,j;
19     int len1=strlen(s1);
20     int len2=strlen(s2);
21     while(scanf("%s%s",s1,s2)!=EOF)
22     {
23         memset(dp,0,sizeof(dp));
24         len1=strlen(s1);
25         len2=strlen(s2);
26         for(i=0;i<len1;i++)
27             for(int j=0;j<len2;j++)
28         {
29             if(s1[i]==s2[j]) dp[i+1][j+1]=dp[i][j]+1;
30             else
31             {
32                 dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
33             }
34         }
35         printf("%d\n",dp[len1][len2]);
36     }
37     return 0;
38 }