經(jīng)典DP問(wèn)題
#include <stdio.h>
#include <string.h>
#define N 1005
#define MAX(a, b) (a > b ? a : b)
int a[N][N];
int main()
{
char s1[N], s2[N];
memset(a, 0, sizeof(a));
while(~scanf("%s %s", s1, s2))
{
int l1 = strlen(s1);
int l2 = strlen(s2);
for(int i = 0; i < l1; i++)
for(int j = 0; j < l2; j++)
{
if(s1[i] == s2[j]) a[i + 1][j + 1] = a[i][j] + 1;
else a[i + 1][j + 1] = MAX(a[i][j], MAX(a[i][j + 1], a[i + 1][j]));
}
printf("%d\n", a[l1][l2]);
}
return 0;
}