【魔怔向】致远DP学习笔记

卷首语

非淡泊无以明志，非宁静无以致远。——诸葛亮《诫子书》

致远DP是用来解决一类特定的动态规划问题的方式，其核心思想是在维护最小值信息时利用好题目的特殊性，让下标参与到最小值信息的维护中。

其最早被OI选手葛致远提出。

而且结合了贪心的思路设计dp，诠释了非宁静无以致远的重要内涵和深刻思想。

在正式介绍致远DP之前，让我们先来看一道例题。

有长度为 $n$ 的序列 $a$ ，判断 $a$ 是否可以拆成两个上升子序列。

每个 $a_i$ 都得属于其中一个上升子序列。

$n\leq10^6$

考虑从前往后扫碰到 $a_i$ 的时候， $a_i$ 一定会成为一个上升子序列的最后元素，因此，我们只需要让另一个上升子序列最后的元素最小，即可满足最优性。

设计dp。

$dp(i)$ 表示前 $i$ 个数拆成两个上升子序列， $a_i$ 不在的那个的末尾最小是多少。

转移的时候从 $dp(i-1)$ 得来。

如果 $a_i$ 两个都能接上，接在大的后面。

只能接一个，就接在它后面。

都接不了，那就不能拆成两个上升子序列。

时间复杂度： $O(n)$

容易发现，致远DP其实是基于贪心设计的一种DP。

往往能在将序列拆分为两个子序列的问题中有着很好的表现。

其核心思想可以概括为淡泊明志，宁静致远。

淡泊明志指的是将其中一个子序列用下标来进行限制，朴素而又明确。

宁静致远指的是基于子结构最优性能和全局最优性相统一，以贪心的思想稳步得到最优解。

将这个模型隐藏在题目表象之后或将两个子序列设置更强的限制，致远DP就能用来解决更难的问题。

接下来进入 3 个例题的讲解。