wzf2000 数据结构与算法教程之动态规划（3）——LIS 与 LCS
Contents
动态规划
根据百度百科的分类，我们还有树形 dp，线性 dp 以及区域 dp。
当然这个分类本来用来学习就不太靠谱。
我们还是按照某张图片来学习，这次讲一些动态规划中的常见模型。
最长上升子序列（LIS）
问题简述
考虑这样一个问题：
我们有一个 $n$ 个数的有序数组，我们希望取出一个其中的一个子序列（大概就是有限数列中的子列），使得其中的元素（严格）单调递增。
直接想法：动态规划
根据前面的学习，我们大概已经有了一些动态规划设计状态的思想。
这里假设给出的数组为 $a[1…n]$。
一个较为简单的想法就是，$f[i]$ 表示以 $a[i]$ 结尾的最长上升子序列的长度。
很容易得出转移：先枚举 $i$，枚举上一个结尾的位置 $j$，判断是否满足 $a[i] >(\ge) a[j]$，如果满足则尝试更新 $f[i]$。
这个算法显然是 $O(n^2)$ 的时间复杂度。
考虑到很有可能序列长度 $n$ 极大，还是需要尝试优化算法。
改进方法：贪心的应用
下面的算法针对严格增的版本，非严格也同理。
假设我们已经处理完了 $n$ 个数中的前 $i$ 个，此时前 $i$ 个应该有许多不同长度不同元素的上升子序列。
但是对于相同长度的上升子序列，实际上只有其最后一个也就是最大的元素对之后的元素会产生影响。（上面的转移只用到了上一个结尾的值）
而相同长度，显然最后一个越小越优，毕竟可以挑更小的后一个，限制更少。
所以我们可以用 $Min[j]$ 表示到目前为止（处理完前 $i$ 个），长度为 $j$ 的上升子序列的末尾元素的最小值。
而这个数组显然是单调增的（不严格），证明可以考虑反证。
如果所有的 $Min[j]$ 都满足 $Min[j] < a[i]$，也就是说加入 $a[i]$ 必然能延长上升子序列，则就让当前最大的长度 L++，并且 Min[L]=a[i] 即可。
否则我们无法让 LIS 长度增加，且必定存在若干个 $Min[j]$ 满足 $Min[j] \ge a[i]$，那么这些 $j$ 一定是最大的若干个（根据前面所说的单调增），设最小的 $j$ 为 $k$，那么也就是说 $Min[k – 1] < a[i] \le Min[k]$，这样我们就可以用 $Min[k - 1]$ 对应的序列加上 $a[i]$ 获得一个末尾元素更小的长度为 $k$ 的序列，也就是更新 $Min[k] = a[i]$。对于长度小于 $k$ 的序列，显然这个元素并不能让其的最末尾元素变小，而对于长度大于 $k$ 的序列，设其长度为 $l(l > k)$，则若存在一个 $l – 1$ 的序列可以在之后再加上一个 $a[i]$，那么有 $Min[l – 1] < a[i]$，这与 $Min[l - 1] \ge Min[k] \ge a[i]$ 矛盾。所以实际上对于每次新加入的元素 $a[i]$，只会最多更新一个 $Max[k]$，而对应的位置 $k$ 的寻找显然可以使用二分法。
可以发现，这个算法的时间复杂度是 $O(n \log n)$，空间复杂度依然是 $O(n)$，可以说非常好地优化了原先的动态规划。
代码实现
L=0;
for (int i=1;i<=n;i++)
{
if (!L||a[i]>Min[L]) Min[++L]=a[i];
else
{
int l=1,r=L,ret=0;
while (l<=r)
{
int mid=(l+r>>1);
if (a[i]<=Min[mid]) ret=mid,r=mid-1;
else l=mid+1;
}
Min[ret]=min(Min[ret],a[i]);
}
}
// 最终的 L 即为 LIS 长度
拓展
这个算法同样还能求出某一个 LIS 中的各个元素，只需要将 $Min$ 数组改为存储数组下标即可，这里不做具体讲解。
当然既然是贪心（尽管我们还没讲过贪心是啥），这个算法自然是有其弊端的——无法求出 LIS 的数量。
当然了，原来的动态规划方法还是可以的，但是复杂度有点高。
这里一般会用数据结构维护 $f[i]$ 来使得找到最大的复杂度降为 $O(\log n)$。
当然了，因为我们没有学过包括线段树、树状数组这类数据结构，也没有学过 cdq 分治等算法，所以不具体讲。
除此之外，这个算法也可以应用到二维偏序的情况。
二维偏序是指，两维同时满足大小关系的一种偏序。
我们只需要将一维排序，那么对于另一维进行 LIS 的计算，实际上就是二维偏序下的最长单调链。
练习题
最长公共子序列（LCS）
问题简述
这一次，我们会拥有两个数组，我们希望找到最长的一个子序列，使得其同时是两个数组的子序列。
暴力想法
直接考虑状态。
假设用 $f[i][j]$ 表示第一个数组到第 $i$ 个数，第二个数组到第 $j$ 个数，最大的公共子序列长度。
那么如果 $a[i] = b[j]$ 则 $f[i][j] = \max(f[i – 1][j – 1] + 1,f[i – 1][j],f[i][j – 1])$。
否则 $f[i][j] = \max(f[i – 1][j],f[i][j – 1])$。
这样时空复杂度均为 $O(n^2)$。
可能的优化
一般来说，达到上面这个复杂度已经比较可以接受了，毕竟是对两个数组的询问。
当然，对于一些特殊情况，我们还是有操作的。
首先对于 $b[i]$ 未在 $a[i]$ 中出现的数，显然可以剔除（同理 $a[i]$ 也一样）。
这样，剩下的 $b[i]$ 必定在 $a[i]$ 中有一个出现位置的集合。
比如设 $a[] = \{1,3,1,2,3\},b[] = \{1,3\}$。
则 $b[1] = 1$ 的出现位置集合就为 $\{1,3\}$，$b[2] = 3$ 的出现位置集合就为 $\{2,5\}$。
我们每个集合中的数从大到小排序，然后将每个集合代替原先 $b[i]$ 中的数。
比如上例中，新得到的序列就是 $3,1,5,2$。
那么，我们可以得出一个结论：
$a,b$ 两个数组的最长公共子序列长度即为新得到序列的 LIS 长度。
证明需要将两边一一对应，过程比较简单，利用一下位置集合的倒序就差不多了，这里留作思考。
然后分析一下复杂度，大概就是对于新序列求 LIS 的复杂度。
所以说复杂度取决于新序列的长度。
如果是最坏情况，新序列大致能达到 $O(n^2)$ 的长度，这样复杂度也就是 $O(n^2 \log n)$，甚至劣于暴力。
但是如果数据随机，或者保证每个数平均出现 $O(1)$ 次，可以发现复杂度降到了 $O(n \log n)$。
总而言之，这个算法十分依赖于数据的特殊性。
代码实现
因为暴力较简单且优化算法时间复杂度不严格，所以不附代码。
No Comments