最长上升子序列案例教学探析

本文结合两个经典例题和一个最长公共子序列变型题,呈现最长上升子序列的建模和优化过程,并给出解决最长公共子序列问 题(LCS)的新思路。

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

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