Loading [MathJax]/jax/output/HTML-CSS/jax.js

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

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

动态规划

根据百度百科的分类,我们还有树形 dp,线性 dp 以及区域 dp。

当然这个分类本来用来学习就不太靠谱。

我们还是按照某张图片来学习,这次讲一些动态规划中的常见模型。

最长上升子序列(LIS)

问题简述

考虑这样一个问题:

我们有一个 n 个数的有序数组,我们希望取出一个其中的一个子序列(大概就是有限数列中的子列),使得其中的元素(严格)单调递增。

直接想法:动态规划

根据前面的学习,我们大概已经有了一些动态规划设计状态的思想。

这里假设给出的数组为 a[1n]

一个较为简单的想法就是,f[i] 表示以 a[i] 结尾的最长上升子序列的长度。

很容易得出转移:先枚举 i,枚举上一个结尾的位置 j,判断是否满足 a[i]>()a[j],如果满足则尝试更新 f[i]

这个算法显然是 O(n2) 的时间复杂度。

考虑到很有可能序列长度 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]a[i],那么这些 j 一定是最大的若干个(根据前面所说的单调增),设最小的 jk,那么也就是说 Min[k1]<a[i]Min[k],这样我们就可以用 Min[k1] 对应的序列加上 a[i] 获得一个末尾元素更小的长度为 k 的序列,也就是更新 Min[k]=a[i]。对于长度小于 k 的序列,显然这个元素并不能让其的最末尾元素变小,而对于长度大于 k 的序列,设其长度为 l(l>k),则若存在一个 l1 的序列可以在之后再加上一个 a[i],那么有 Min[l1]<a[i],这与 Min[l1]Min[k]a[i] 矛盾。所以实际上对于每次新加入的元素 a[i]只会最多更新一个 Max[k],而对应的位置 k 的寻找显然可以使用二分法

可以发现,这个算法的时间复杂度是 O(nlogn),空间复杂度依然是 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 长度
C++

拓展

这个算法同样还能求出某一个 LIS 中的各个元素,只需要将 Min 数组改为存储数组下标即可,这里不做具体讲解。

当然既然是贪心(尽管我们还没讲过贪心是啥),这个算法自然是有其弊端的——无法求出 LIS 的数量。

当然了,原来的动态规划方法还是可以的,但是复杂度有点高。

这里一般会用数据结构维护 f[i] 来使得找到最大的复杂度降为 O(logn)

当然了,因为我们没有学过包括线段树、树状数组这类数据结构,也没有学过 cdq 分治等算法,所以不具体讲。

除此之外,这个算法也可以应用到二维偏序的情况。

二维偏序是指,两维同时满足大小关系的一种偏序。

我们只需要将一维排序,那么对于另一维进行 LIS 的计算,实际上就是二维偏序下的最长单调链。

练习题

POJ1631

最长公共子序列(LCS)

问题简述

这一次,我们会拥有两个数组,我们希望找到最长的一个子序列,使得其同时是两个数组的子序列。

暴力想法

直接考虑状态。

假设用 f[i][j] 表示第一个数组到第 i 个数,第二个数组到第 j 个数,最大的公共子序列长度。

那么如果 a[i]=b[j]f[i][j]=max(f[i1][j1]+1,f[i1][j],f[i][j1])

否则 f[i][j]=max(f[i1][j],f[i][j1])

这样时空复杂度均为 O(n2)

可能的优化

一般来说,达到上面这个复杂度已经比较可以接受了,毕竟是对两个数组的询问。

当然,对于一些特殊情况,我们还是有操作的。

首先对于 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(n2) 的长度,这样复杂度也就是 O(n2logn),甚至劣于暴力。

但是如果数据随机,或者保证每个数平均出现 O(1) 次,可以发现复杂度降到了 O(nlogn)

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

代码实现

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

练习题

洛谷 1439

其他相关练习题

HDU 1423 LCIS

Codeforces 249D

 

点赞 0

No Comments

Add your comment

连雨不知春去,一晴方觉夏深。