数据结构与算法教程之动态规划（3）——LIS 与 LCS

wzf2000
2019年11月9日

数据结构与算法教程之动态规划（3）——LIS 与 LCS

动态规划

根据百度百科的分类，我们还有树形 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 的计算，实际上就是二维偏序下的最长单调链。

练习题

POJ1631

最长公共子序列（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)$。

总而言之，这个算法十分依赖于数据的特殊性。

代码实现

因为暴力较简单且优化算法时间复杂度不严格，所以不附代码。

练习题

洛谷 1439

其他相关练习题

HDU 1423 LCIS

Codeforces 249D

 教程 数据结构与算法