基于状态压缩的最长公共上升子序列快速算法-《计算机技术与发展》

文章信息/Info

Title:: A Longest Common Increasing Subsequence Algorithm Based on State Compression

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

Abstract:: Discussed the problem of a Longest Common Increasing Subsequence ( LCIS) ,put forword a fast dynamic algorithm for LCIS. For the LCIS problem,used respectively the algorithm of a Longest Common Subsequence ( LCS) combined a Longest Increasing Subse-quence (LIS) algorithm,dynamic programming algorithm,improved dynamic programming algorithm through state to design,and per-formed the second and the third algorithm. The designed state compressed dynamic programming algorithm realized a fast solution for LCIS. According to analyze the time and space complexity of the three algorithms,presented a fast algorithm for delivering a longest com-mon increasing subsequence in O( mn) time and O( m) or O( n) space finally.