动态规划中最长公共子序列问题

最长公共子序列问题（LCS problem）是一个典型的体现经典动态规划思路的算法核心问题，在具体表述上则是要求找出两个或多个序列中存在的一个最长的连续子序列。

给定两个子序列X={x1,x2,x3...xm}和Y={y1,y2,y3,...yn}。求X和Y长度最长的公共子序列。

对于该问题而言，在采用暴力搜索方法进行求解时，则必然需要遍历所有可能的X子集。随后会对每一个这样的X子集进行判断以确定其是否为Y的一个有效子序列，并将找到的结果记录为最长匹配结果。每个这样的X子集对应一个下标集合{1,2,…,m}的不同组合情况；因此共有2^m个可能不同的组合情况需要逐一考察。由于其计算复杂度呈指数增长特性，在实际应用中这种方法在处理较长的数据时效率会显著降低而不再具有可行性；因此我们需要寻找更高效的解决方案以解决这一问题

那么，我们可不可以采用动态规划思想来求解此类问题呢？

我们先来复习一下使用动态规划所要满足的条件。

最优子结构特性是最优化原则的核心内容。 最优子结构特性可这样描述：对于任何一个最优化策略，在其初始状态确定后形成的决策序列必定包含一系列局部最优的选择。 简单来说，则是任何问题若满足这一原则都可通过分析其局部结构来求解全局问题。同样地，在数学规划领域内任何一个具备这种性质的问题都可通过分解为较小规模的子问题来实现全局最优。

无后效性是指在各个阶段按