#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);其实这是最正常的路径压缩，这样少了好多内存~不过，压缩带来的后果就是会损失信息。

• Re:第一次自己做路径压缩~0MS~ (23) jhldreams 2014-07-17 22:55:18
• 这个不是路径压缩。是滚动数组 (818) yygy 2014-07-17 23:25:04