本讲我们来探讨动态规划算法中一个常见的问题最长公共子序列即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)等之间的关系。
