最长公共子序列问题
动态规划的一个计算两个序列的最长公共子序列的方法如下： 以两个序列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)。
下载地址
用户评论
运行没问题，就是描述过少
运行正确，谢谢分享
对我帮助很大
还行，很喜欢
能运行成功，让我顺利交了报告
运行正确，代码效率较高
运行正确，可以使用。谢谢分享。