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

• 作者: 郭冬梅
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 最长公共上升子序列 最长公共子序列 最长上升子序列 动态规划 状态压缩
• 年，卷（期）: 2014,（5）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 40-43
• 页数: 4页
• 分类号: TP391
• 字数: 4025字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2014.05.010

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郭冬梅	安徽理工大学计算机科学与工程学院	14	49	5.0	6.0