算法简述
最长上升子序列(Longest Increasing Subsequence, 简称LIS)是dp中比较经典的一个算法模型, 它有一种朴素的算法O(n^2)和一种优化版的算法(nlogn)实现, 通过它, 我们可以进一步了解dp的思想.
题目链接
pku-2533 Longest Ordered Subsequence
题意
给定一个长度为1000以内的数组,每个元素范围都在[0,10000]的整数,求这个数组的LIS.
解法
记数组为a[0...n-1],算法很直接,具体如下:
- 状态定义:
dp[i]代表以第i项为结尾的LIS的长度. - 状态转移:
dp[i] = max(dp[i], max(dp[j]) + 1) if j < i and a[j] < a[i] - 状态初始化:
dp[i]=1 - 时间复杂度:
状态数为n, 每次转移复杂度是O(n), 所以算法总复杂度是O(n^2)
核心代码：
for(i = 0; i < n; ++i) {
for(j = 0; j < i; ++j) {
if(a[j] < a[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
算法优化
再来看一道题:
题目链接:
题意:
这题是一个经典的布线问题, 如下图所示: 左右各有n(n<40000)个点, 原本左边的每个点分别跟右边的一个点相连(不会有两个左边的点连同一个右边的点), 要求我们拆除一部分线, 保留尽可能多的线, 使得剩下的线两两不能有交点.
解法:
记左边的两个点为i, j且i < j, 与之相连的右边的点分别为a[i], a[j], 则两条线不相交的充要条件就是: a[i]<a[j], 于是这个问题转化成了经典的LIS.
但是这题与上题最大的差别就在于: 数组的长度太大了, 由1000变到了40000, 于是O(n^2)复杂度基本只有超时的命运, 所以我们必须想办法优化.
更优的算法
下面介绍一种O(nlogn)的LIS算法:
- 记数组为a[0...n-1];
- 状态定义:
dp[i]代表LIS的第i项最小值, dpLen代表当前dp数组的长度; - 状态转移:
dp初始为空数组, 我们按a数组元素的下标顺序进行扫描, 假设现在扫描到a[i], 先找到dp数组中第一项大于或等于a[i]的元素, 记为dp[j]; 将dp[j]更新成a[i]即可; 如果dp数组中没有元素比a[i]大的话, 那么直接将a[i]插入到dp数组的尾部,再更新dp数组长度; - 整个数组的LIS结果就是dpLen.
- 需要注意的是, 虽然dp数组最终长度就是LIS, 但是里边的元素并不是真正的子序列, 如果要求输出这个序列, 加上一些反向追踪变量就能得到了. 但是如何求LIS的数量呢?
- 刚开始dp数组为空,显然是单调递增数组, 而后面的每一步替换或者尾部插入执行都不影响其单调递增的特性, 所以每次定位到dp[j]可以用二分法, 复杂度是 O(logn)
- 整体算法复杂度:
状态转移次数为n, 每次状态转移代码都是logn, 所以总复杂度为O(nlogn).
算法步骤示例:
假设a = [4, 2, 6, 3, 1, 5], 初始dp=[], 具体算法运行步骤如下:
- a[0]=4 => dp=[4];
- a[1]=2 => dp=[2];
- a[2]=6 => dp=[2, 6];
- a[3]=3 => dp=[2, 3];
- a[4]=1 => dp=[1, 3];
- a[5]=1 => dp=[1, 3, 5];
所以这个a数组的LIS就是len(dp)=3. 从运行步骤里可以看出, 如果一个数很小, 可以作为LIS的头部或者中部, 让后面的数字更容易接到它后面, 以此增大LIS长度; 而一个数非常大, 则可以很容易接到LIS的尾部, 也一样能增大LIS长度; 所以让它们找准自己的定位还是非常重要的.
核心代码:
dpLen = 0;
for (i = 0; i < n; ++i) {
int idx = lower_bound(dp, dp + dpLen, a[i]) - dp;
dp[idx] = a[i];
if (idx + 1 > dpLen) {
dpLen = idx + 1;
}
}
完整代码
ps: Java里没有提供类似lower_bound或者upper_bound
之类的方法, 还是挺遗憾的, 所以这题代码就用C++了.
