問題：任意輸入兩個字符串，求這兩個字符串之間的最長子序列（LCS）。。。。

在解題之前，需要理解幾個定理：
X=<x1,x2,x3...xn>,Y=<y1,y2,y3...ym>
X,Y的1最長子串表示為： LCSxy

假設(shè) Z=<z1,z2,z3...zk>是X,Y的任意子串，
那么：
1,當(dāng)xn=ym時，zk=xn=ym, LCSxy=LCS(x-1)(y-1) + 1
2,當(dāng)xn！=ym時， zk!=xn LCSxy=LCS(x-1)y
zk!=ym LCSxy=LCSx(y-1)

python實現(xiàn)：

20150827201234.png