4-5最长公共子序列问题算法分析

动态规划的一个计算两个序列的最长公共子序列的方法如下：　　以两个序列X、Y为例子：　　设有二维数组f[i,j]表示X的i位和Y的j位之前的最长公共子序列的长度，则有：　　f[1][1]=same(1,1);　　f[i,j]=max{f[i-1][j-1]+same(i,j),f[i-1,j],f[i,j-1]}　　其中，same(a,b)当X的第a位与Y的第b位完全相同时为“1”，否则为“0”。　　此时，f[j]中最大的数便是X和Y的最长公共子序列的长度，依据该数组回溯，便可找出最长公共子序列。　　该算法的空间、时间复杂度均为O(n^2)，经过优化后，空间复杂度可为O(n)。