动态规划算法-LCS

动态规划算法-LCS

本讲我们来探讨动态规划算法中一个常见的问题最长公共子序列即LCS(Long Common Sequence)。 首先我们来看一下问题描述： 有两个序列X和Y，其中 X = {x1, x2, ..., xm} Y = {y1, y2, ..., yn} 求X和Y的最长公共子序列长度。   例如：X={1, 3, 5, 9, 10}  Y={1, 4, 9, 10}，则X和Y的最长公共子序列的长度为3，其中一个序列为{1，9，10}。   解题思路：   步骤1：用函数的形式来表示结果。 设f(x,y) = z，该函数表示X序列的长度为x, Y序列的长度为y，则XY序列的最长公共子序列长度为z。 所以题目要求解的便是f(m,n)的值。   步骤2：分析递推情况。 接下来我们来分析一般情况即f(i,j)的求解。 f(i,j)表示有两个序列 X = x1, x2, ..., xi Y = y1, y2, ..., yj 如何求这两个子序列的最长公共子序列的长度。   所谓的递推关系分析其实就是分析f(i)与f(i-1)、f(i-2)...或f(0)等之间的关系，由于本题是二元函数关系，故就是分析f(i,j)与f(i-1,j-1)、f(i-1,j)、 f(i, j-1)等之间的关系。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。