基于状态压缩的最长公共上升子序列快速算法

摘要：

探讨了最长公共上升子序列(LCIS)问题，在前人算法的基础上提出一种高效求解LCIS的动态规划算法。对于LCIS问题，分别使用最长公共子序列(LCS)和最长上升子序列(LIS)相结合的算法、动态规划算法、经过状态压缩的改进动态规划算法进行设计，并对后两种算法进行了实现。设计的状态压缩的动态规划算法，实现了LCIS的快速求解。通过分析这三种算法的时间和空间复杂度，最终提出了时间复杂度为O(mn)、空间复杂度为O(m)或O(n)的基于状态压缩的快速LCIS算法。

关键词：最长公共上升子序列、最长公共子序列、最长上升子序列、动态规划、状态压缩

分类号：TP391(计算技术、计算机技术)

资助基金：安徽省高等学校省级优秀青年人才基金项目2011SQRL040;安徽理工大学青年教师科学研究基金2012QNY31

在线出版日期：2014-05-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：40-43