本文共 1312 字，大约阅读时间需要 4 分钟。

动态规划中的最长上升子序列模型

最长上升子序列（Longest Increasing Subsequence，LIS）是一个经典的动态规划问题，广泛应用于许多领域。其解决方法主要包括动态规划和贪心算法，涉及树状数组等高级数据结构优化。

涉及的知识点总览

主要涉及的算法知识点有：

最长上升子序列的DP数组优化

在传统的$O(N^2)$解法中，数组f[i]表示以i结尾的最长上升子序列的长度。其更新规则为：

$$ f[i] = \max_{j < i \text{且} a[j] < a[i]} (f[j] + 1) $$

这个过程从前往后或从后往前遍历数组，时间复杂度为$O(N^2)$。传统实现的局限性在于其较高的时间复杂度。

使用树状数组优化

为了减少时间复杂度，可以使用树状数组（Binary Indexed Tree，Fenwick Tree）进行优化。树状数组可以高效处理范围查询和更新操作，使得$O(N \log N)$的时间复杂度成为可能。

优化方法如下：

该方法通过树状数组有效地维护了序列的状态，避免了传统方法中重复计算的高额开销。

##怪盗基德的滑翔翼

怪盗基德问题是求最长下降子序列的长度（或最长上升子序列的长度）。其解法可以分为两种：

登山问题

登山问题要求正反两次求解最长上升子序列，并输出每个点的位置。

• 动态规划方法：$O(N^2)$。
• 树状数组加速方法：通过先后处理两个方向的动态规划结果，达到$O(N \log N)$复杂度。

合唱队形

合唱队形问题实际上是相同目标，但变为了最小化结点数。本质上仍然解释为求最长上升子序列问题。

• 动态规划方法：$O(N^2)$。
• 贪心加速优化：$O(N \log N)$。

##友好城市问题

友好城市问题转化为求最长不递减子序列的问题。

• 动态规划方法：$O(N^2)$。
• 贪心加速方法：通过排序两边维护长度记录。

最大上升子序列和

最大上升子序列和问题的挑战在于不能直接使用常规LIS算法。

• 动态规划方法：直接遍历计算，$O(N^2)$复杂度。
• 贪心方法：由于子序列的和并非连续，无法直接使用LIS的贪心优化。

拦截导弹问题

拦截导弹问题的问题转化为求最小的拦截组或最多的不递增子序列。

• 解法：使用贪心算法，类似于LIS的树状数组优化，$O(N \log N)$复杂度。

Dilworth定理的应用

Dilworth定理：对于任意偏序集，最长链的长度等于最少反链划分数。

• 该定理在LIS问题中的应用为：最长反链对应最少拦截组。

本文详细阐述了最长上升子序列问题在不同变种下的解决方法及其优化技术，涵盖了动态规划、贪心算法和树状数组等技术的应用。

转载地址：http://suxpz.baihongyu.com/