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

A Longest Common Increasing Subsequence Algorithm Based on State Compression

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

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.