问题与基本方法
定义 2.4.1
(严格递增子序列与最长递增子序列问题)
设 是取值属于全序集合的有限序列。严格递增子序列选取下标 ,并要求 ;所选位置不必相邻,也不能重复选取同一个值。问题是求一个长度 最大的这类子序列(称为解)及其长度。当 ,答案是长度 及空解。
下文计算数值比较次数,并假设每次比较耗时为常数。直接的动态规划清楚展示状态的选择:状态必须记录子序列在哪里结尾,因为只有最后一个值才限制它如何延长。
定理 2.4.2
(最长递增子序列的二次动态规划)
对 ,令 为以下标 结尾的严格递增子序列之最大长度,则
当 ,最优长度是 。对每个 的 ,存储一个达到最大值的下标 ,再由达到 的下标沿这些存储的下标回溯并反转,便得到一个解。此方法使用 次比较及 空间。
证明
(按结尾下标归纳)
固定 ,取一个以 结尾、长度达到 的子序列。若它只有一项,则 ,而由下面的反向不等式可知不存在合格的 。否则它有倒数第二个下标 ,且 ;其前 项构成以 结尾的严格递增子序列,故 。反过来,对任何满足 及 的 ,在以 结尾的最优子序列后加上 是合法的,长度为 ,故 。两个方向合起来,按 归纳便证得递推式; 处理不存在合格 的情形。
每个严格递增子序列都在某处结尾,因此最优长度是 。对 的下标 ,沿所存储的前驱走一步,会到达 值恰好小一的下标,所以走 步后到达 的下标;将收集到的下标反转,便得到递增的下标及严格递增的值。需要比较的下标对 至多有 个,而数组 与指针都只有 项。
概念视角组合
位置图上的最长路径
当 且 时,画一条边 。一列下标是有向路径,当且仅当每对相邻下标在位置和数值上都递增;把不等式连起来,这与“严格递增子序列”完全相同。因此问题就是这个无环图上的最长路径问题, 是以 结尾的路径所含顶点数的最大值。递推式就是按下标次序计算最长路径的常用递推式,而二次的比较次数,就是检视每条可能的边的代价。下一节的方法并不建立这个图。
快速检查
(求序列 的 ,并写出最优长度。)
由左至右套用递推式。
解答 · 答案
。 只有 合格,故 。 同样只有 合格,故 。 之前的值都较小,而 ,故 。最优长度是 ,例如 或 。
最小末尾值与二分搜索
如果只需长度,可压缩所需信息。
定义 2.4.3
(最小末尾值清单)
固定前缀 ,令 为其中严格递增子序列的最大长度。对每个 ,最小末尾值 是此前缀中长度为 的严格递增子序列之末尾值的最小值。由于前缀有限,每个最小值都存在;又因为长度 的子序列有每个较短长度的前缀,所以每个 都有子序列达到。最小末尾值清单是 ;当 时为空。
定理 2.4.4
(最小末尾值不变量与更新规则)
设 是前缀 的最小末尾值清单,则 。令 ,并令 为第一个满足 的下标;若没有,取 。前缀 的最小末尾值清单,是将 设为 ( 时为新增的最后一项),其余各项不变而得。因此处理完整个输入后,清单的长度就是最优长度。
证明
(只有一项会改变)
严格性。 达到 的子序列,其长度 前缀的末尾较小,因此 。
哪些长度能以 结尾。 旧的子序列在较长前缀中仍然存在,所以各项只会变小;变小需要新的子序列,它必须以下标 (值为 )结尾。设这样的子序列长度为 。删去最后一项,便得到旧前缀中长度 、末尾值小于 的子序列,所以 。由于 严格递增,小于 的项恰是 ,故 ,即 。另一方面,若 ,则 ,在达到 的子序列后加上 ,便得到以 结尾、长度为 的子序列;若 ,单项 的长度为一。所以以 结尾的子序列可有直至 的每个长度,却不会更长。
对各项的影响。 当 ,已有 ,故以 结尾的新子序列无法降低 。当 ,不存在该长度的新子序列。当 ,新候选值 满足 ,故该项变为 (若 则不变)。若 ,新清单多一项 ;不可能形成更长的子序列,因为旧前缀的最大长度是 。从空前缀出发按 归纳,便证得此规则,而最后的 就是最优长度。
证明透视
更新规则的力量从何而来
唯一不显然的一步,是只用一个比较 ,便为每个新子序列的长度定出上界 。清单的严格性被用了两次:它使小于 的项构成清单的一段前缀,所以可以用二分搜索找到分界点 ;它也把界 化为 。问题本身的严格性则通过分界点的选择进入论证:等于 的项并不小于 ,因此不会被延长,而是由 取代,而不是产生更长的子序列。论证得以完结,是因为 、、 三种情形涵盖每一项,而只有 会改变。
这里使用下界搜索,即寻找首个末尾值至少为 的位置。相等值不得延长严格递增序列的长度;本更新规则会替换相等的末尾值。若要求非递减子序列,则应改找首个严格大于 的末尾值,并相应修改不变量和比较;两种规格不能互换。
反例模式
用上界搜索会算出错误的长度
假设改为搜索首个严格大于 的末尾值,但规格仍是严格递增。对 ,清单起初为空,第一个 被新增:。第二个 没有严格更大的末尾值,因此再次新增:,第三个 使清单成为 。此方法报告长度 ,但严格递增子序列不能重复同一个值,真正的最优长度是 。修正方法是采用更新规则中的下界搜索:第二个和第三个 ,首个至少为 的末尾值都是 ,所以 被 取代,清单保持 ,长度为 。上界搜索版本算出的其实是最长非递减子序列的长度。
重构真正的子序列
中的值本身未必按输入次序出现。例如输入 的最终清单是 ,但 在 之后。要重构解,存储 ,即实现目前 的某个子序列的末尾下标,并为每个已处理位置存储不可变的前驱指针 。
命题 2.4.5
(以前驱指针重构解)
处理项目 、分界点为 时,若 便令 ,若 则令 (终止标记),然后令 。处理完最后一项后,从 沿指针回溯至 ,再将收集到的下标反转。当 ,结果是长度恰为 的严格递增子序列,因此是一个解。当 ,直接返回空序列,不查找 。整个方法使用 次比较及 空间。
证明
(指针记录长度逐步减一的链)
断言:任何时刻, 都是某个长度为 、末尾值为 的严格递增子序列的末尾下标,而由 出发的指针链列出它的 个下标。处理项目 时, 所指的子序列末尾值为 ,且其末尾下标早于 ,所以所存储的前驱 早于 ,其值也严格较小。先前存储的指针 从不被改写,因此把 设为 时,由 出发的链不变;由 出发的链比由 出发的链多一个下标,总共 个。按已处理的项目归纳便证得断言,而最后由 出发的链有 个下标,反转后下标递增、值严格递增。
每个项目的二分搜索使用 次比较,故总共 次。数组 、、 都只有 项。这些界限假设比较及下标操作均耗常数时间。
反例模式
末尾值清单不是解
断言:最终的末尾值清单本身就是一个最长递增子序列。对输入 ,清单依次为 、、,最终清单 的长度 是正确的。但输入中 在 之后,所以 并不是子序列;长度为二的严格递增子序列只有 。所存储的下标 同样显示失败,因为下标 并不小于下标 。修正靠已存储的指针:项目 (值为 )存储了 ,从 沿指针回溯得到下标 ,即解 。
例题
例题 2.4.6
(七项输入的最小末尾值与解)
依次处理 。最小末尾值清单依次为
最终长度是 。由最后一项的已存储指针回溯得到 ,所以一个解是 ,下标为 。此处末尾值清单碰巧构成子序列;正如上面的反例所示,这并非一般保证。
例题 2.4.7
(四个数值的二次表格)
对 由左至右计算 。。 之前没有更小的值,故 。 只有 合格,故 ,前驱为 。 同样只有 合格,故 ,前驱为 。最优长度是 。沿下标 的指针得到下标 ,即解 ;沿下标 的指针得到下标 ,即解 。两者都是最长的,可见解并不唯一。
例题 2.4.8
(边界情形:空输入与重复值)
当 ,清单保持为空,长度为 ,解为空,也不查找 。
对 :清单依次为 、;处理第二个 时,首个至少为 的末尾值是 ,所以 被相等的值 取代,清单仍是 ,而 变为下标 。处理值 时,没有末尾值至少为 ,故 ,清单成为 ,且 。指针给出链 ,所以解的下标是 ,值为 。重复的 只被使用一次,长度为 。
常见错误
常见错误
(以最后一个状态代替最大状态作答)
状态 描述恰好以 结尾的子序列,所以答案是 ,而不是 。对 ,各状态为 ,因为 之前没有更小的值。最后一个状态是 ,但最优长度是 ,在下标 达到。
常见错误
(处理完才从末尾下标数组读取前驱)
后来的项目可能覆写 (),所以最终的数组 并不是一条位置链。对 ,处理过程中 依次为 、、,最后是 。下标 并非递增。项目 的前驱在处理它时已存储为 ,链 给出正确的解 。必须在处理项目 的当时存储 。
习题
快速检查
(对 套用严格递增算法,求长度并与最长非递减长度比较。)
使用下界搜索。
解答 · 答案
严格递增长度是 :每个新的 都替换第一个末尾值。非递减长度是 ,因为三个相等值都可依次选取。
快速检查
(逐项计算 的严格最小末尾值清单,给出一个最长解及其下标。)
由左至右处理,每次替换第一个至少等于新值的末尾值。
解答 · 答案
清单为 、、、。最优长度是 ;例如 的下标是 。指针方法也能重构有效的解。
快速检查
(若要求输出实际输入下标,为何只存储最终末尾值不安全?给出本节最短反例,并解释需要什么额外信息。)
把末尾值清单与输入次序比较。
解答 · 答案
对 ,最终末尾值 的输入次序颠倒。存储每个末尾值目前的结尾下标,以及每个已处理位置的固定前驱指针;沿最终下标的指针链回溯,不能直接把末尾值清单当作解。