> #include<stdio.h>
> #include<string.h>
> #include<stdlib.h>
> #include<math.h>
> #include<float.h>
> #include<malloc.h>
> #include<time.h>
> 
> int x[2][1000];
> char s1[1000], s2[1000];
> 
> int max(int x, int y)
> {
> 	return x>y?x:y;
> }
> 
> int main()
> {
> 	int len1, len2, i, j, n;
> 	while(scanf("%s %s",&s1,&s2)!= EOF)
> 	{
> 		memset(x,0,sizeof(x));
> 		len1 = strlen(s1);
> 		len2 = strlen(s2);
> 		n = max(len1, len2);
> 		for (i=0;i<len1;i++)
> 		{
> 			for (j=0;j<len2;j++)
> 			{
> 				if (s1[i] == s2[j])
> 					x[1][j+1] = x[0][j]+1;
> 				else
> 					x[1][j+1] = max(x[1][j], x[0][j+1]);
> 			}
> 			for (j=0;j<len2;j++)
> 				x[0][j+1]=x[1][j+1];
> 		}
> 		printf("%d\n",x[1][len2]);
> 	}
> }
> 
> 把O(m*n)压缩到了O(n);其实这是最正常的路径压缩，这样少了好多内存~不过，压缩带来的后果就是会损失信息。