基本线性DP

基本线性DP

LCS 最长公共子序列

问题描述

给定两个序列A,B,求它们的最长公共子序列,给出长度即可

数据范围

$$|A|, |B| <= 10^{4}$$

Hard : $$|A|, |B| <= 10^{5}$$

求解

先考虑 $$O(|A| * |B|)$$ 传统算法

状态: $$dp[i][j]$$ 表示A序列前 $$i$$ 个元素与B序列前 $$j$$ 个元素的最长公共子序列的长度。

阶段: A,B序列已经处理的长度,即 $$pair(i,\space j)$$

转移: $$dp[i][j] = max(dp[i – 1][j], \space dp[i][j – 1])$$

$$if(A[i] = B[j]), $$

$$then \space dp[i][j] = max(dp[i][j], dp[i – 1][j – 1] + 1)$$

转移的含义:首先 $$dp$$ 值可以从 $$dp[i – 1][j]$$ 和 $$dp[i][j – 1]$$ 继承,然后如果 $$A[i]$$ 等于 $$B[j]$$ ,我们把 $$dp[i][j]$$ 与 $$dp[i – 1][j – 1]$$ 取最大值,因为 $$dp[i – 1][j – 1 ]$$ 继承了 $$A[i]$$ 之前和 $$B[j]$$ 之前的处理情况


考虑优化

我们用一个映射的方法来将LCS转换为LIS问题,具体见我的这篇文章。设构造后长度为 $$n$$ 复杂度可以降至 $$O(nlogn)$$。

我认为如果刻意构造数据的话这种做法可能会被卡掉,比如毒瘤数据是A,B字母全相同,构造出来的序列长为 $$|A| * |B|$$ 导致复杂度变成 $$|A| * |B| * log(|A| * |B|)$$

LIS 最长上升子序列

给定一个序列A,求它的最长的上升子序列,给出长度即可

数据范围

$$|A| <= 10^{5}$$

求解

先考虑 $$O(|A|^{2})$$ 暴力算法

状态: $$dp[i]$$ 表示A序列前 $$i$$ 个元素的L最长上升子序列长度。

阶段: A序列已经处理的长度,即下标$$i$$

转移: $$dp[i] = dp[j] + 1$$ ( $$j \in [1,i) $$ && $$data[j] < data[i]$$)

答案就是 $$dp$$ 取最大值


考虑优化

考虑在整个过程中的两层循环

第一层是阶段的枚举,即 $$for \space \space \space i \space : \space \space 1 \space to \space |A|$$ ,显然枚举阶段是必不可少的 (不然怎么规划啊

第二层是转移的枚举,即 $$for \space \space \space j \space : \space \space 1 \space to \space i \space – \space 1$$ ,注意在这个枚举的过程中我们枚举的大部分数是没用的,因此考虑对转移做优化(魔改)

  • 优化动态规划主要从状态转移入手

对于 $$O(|A|^{2})$$ 的转移,在我们枚举的每一个 $$j$$ 对应的数字中,比 $$data[i]$$ 大的数字没有产生贡献。

再考虑比 $$data[i]$$ 小的数字:如果可以转移,对于我们答案产生贡献一定是能更新出 $$dp_{max} + 1$$ 的情况

对于每个新产生出用来取 $$max$$ 的 $$dp$$ 值(注意是 $$dp$$ 值),可能有很多种转移,但是其实我们只需要从大于 $$data[j]$$ 最小的一个转移过来就可以了。

这样来看,我们可以用一个数组保存与上升子序列长度有关的数据:即长度为 $$len$$ 的最长上升子序列的最小结尾数字

而这个数组里的每个数字只需要是满足条件的所有结尾数字中最小的就可以了,因为一个更小的数字会给更新留下更大空间

重新定义状态: 设 $$dp[len]$$ 表示当前长度为 $$len$$ 上升子序列的最小的结尾数字

阶段仍然是当前已经处理的长度,我们设为 $$i$$,同时还要增加一个 $$max_{len}$$ 表示当前出现的最长上升子序列长度

改进转移: $$i$$ 从 $$1$$ 到 $$|A|$$ ,转移分为两种,如果当前处理到的 $$data[i]$$ 大于 $$dp[max_{len}]$$ ,即可以更新到 $$dp[max_{len} \space + \space 1]$$ ,那么我们把它赋值给 $$dp[max_{len} \space + \space 1]$$ ,否则考虑它能够取代 $$dp[1] ~ dp[max_len]$$ ,显然根据定义, $$dp$$ 值越小越好,因此我们找到大于等于 $$data[i]$$ 的最小 $$dp$$ 值, 然后用 $$data[i]$$ 取代这个 $$dp$$ 值。 (不难证明 $$dp$$ 数组是递增的)


参考资料

Junior Dynamic Programming——动态规划初步·各种子序列问题 _pks ‘w

题解 P1439 – heey

nLogn LCS 算法总结 – non_cease

《算法竞赛进阶指南》 李煜东 著


知识共享许可协议
本作品由kkogoro采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

发表评论

电子邮件地址不会被公开。 必填项已用*标注