一、问题描述
给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)。比如字符串1:BDCABA;字符串2:ABCBDAB。...则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA
二、算法求解
这是一个动态规划的题目。...LCS(Xn-1,Ym)表示:最长公共序列可以在(x1,x2,...xn-1)和(y1,y2,...,ym)中找。...LCS(Xn,Ym-1)表示:最长公共序列可以在(x1,x2,...xn)和(y1,y2,...,ym-1)中找。
求解上面两个子问题,得到的公共子序列谁最长,那谁就是LCS(X,Y)。...因为,当Xn-1和Ym的最后一个元素不相同时,我们又需要将LCS(Xn-1,Ym-1)进行分解:分解成:LCS(Xn-1,Ym-1)和LCS(Xn-2,Ym)
也就是说:在子问题的继续分解中,有些问题是重叠的