最长公共子序列

文章作者 100test 发表时间 2011:03:18 20:31:57
来源 100Test.Com百考试题网

导读:最长公共子序列：一、算法思想，二、源代码，三、运算结果，四、总结分析！

　　一、算法思想

　　一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X 和Y的公共子序列。最长公共子序列就是求给定两个序列的一个最长公共子序列。动态规划可以有效的解决此问题。由最长公共子序列问题的子序列的最优子结构性质，可以建立子问题最优的递归关系。用c[i][j]记录序列Xi和Yi的最长公共子序列的长度，递归关系如下：

　　0 i=0,j=0

　　c[i][j]= c[i-1][j][j-1] 1 i,j