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

数据结构与算法教程之动态规划(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 的计算,实际上就是二维偏序下的最长单调链。

练习题

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

 

点赞 0

No Comments

Add your comment