【动态规划】最长上升子序列(LIS)
2024-08-30 17:03:46
今天看了《挑战程序设计竞赛》的动态规划部分,感觉对以前一些知其然却不知其所以然的问题有了更好的理解,先整理一部分。
题意:
有一个长为n的数列a0,a1,a2,...,an 。请求出这个序列中最长的上升子序列的长度。上升子序列指的是对于任意的i<j都满足ai<aj的子序列。
分析:
设dp[i]为第i个下标之前的子串中最长上升子序列长度。得到递推关系式,时间复杂度O(n2)。
dp[i] = max(dp[i], dp[j] + 1) (a[i] > a[j])
代码:
#include<iostream>
using namespace std;
int a[105], dp[105];
int main (void)
{
int n, ans = 0; cin>>n;
for (int i = 0; i < n; i++) cin>>a[i];
fill(dp, dp + n, 1);
for (int i = 0; i < n; i++){
for (int j = 0; j < i; j++){
if(a[i]>a[j])
dp[i] = max (dp[i], dp[j] + 1);
}
ans = max (dp[i], ans);
}
cout<<ans<<endl;
return 0;
}
分析:
还可以定义dp[i]为长度为i的上升子序列中末尾元素的最小值,对于长度相同的子序列,末尾元素越小,最终获得的上升子序列越可能长。从序列头开始对每个元素a[j]考虑上升子序列长度为0...i的情况,得到递推关系式,时间复杂度O(n2)。
dp[i] = min(dp[i], a[j]) (a[j]>dp[i-1]||i==1)
代码:
#include<iostream>
using namespace std;
const int INF=0x3fffffff;
int a[105], dp[105];
int main (void)
{
int n, ans = 0; cin>>n;
for (int i = 0; i < n; i++) cin>>a[i];
fill(dp + 1, dp + n + 1, INF);
dp[0] = a[0];
for(int j = 0; j < n; j++){
for(int i = 1; i <= n; i++){
if(i == 1||a[j] > dp[i-1])
dp[i] = min(dp[i], a[j]);
}
}
for(int i = n; i >= 1; i--){
if(dp[i] != INF){
cout<<i<<endl;
break;
}
}
return 0;
}
分析:
上述方法中dp数组除INF外单调递增,所以对于每个元素,最多只更新一次dp数组, 而对于这次更新的位置,不必挨个遍历,可以直接二分查找下界,将复杂度降到O(logn)。
代码:
#include<iostream>
using namespace std;
const int INF=0x3fffffff;
int a[105], dp[105];
int _binary_search(int l, int r, int num)
{
while(l < r){ //区间[l,r)
int mid = l + (r - l)/2;
if(dp[mid] >= num) r = mid;
else l = mid + 1;
}
return l;
}//获取下界
int main (void)
{
int n, ans = 0; cin>>n;
for (int i = 0; i < n; i++) cin>>a[i];
fill(dp + 1, dp + n + 1, INF);
for(int j= 1; j <= n; j++){
int pos = _binary_search(1, n+1, a[j]);
dp[pos] = a[j];
}
for(int i = n; i >= 1; i--){
if(dp[i] != INF){
cout<<i<<endl;
break;
}
}
return 0;
}
分析:
可以直接使用STL中的lower_bound获取下界。通过dp数组中INF的下界获取上升子序列长度。为方便表示可直接定义dp[i]为长度为i+1的上升子序列中末尾元素的最小值。有关 lower_bound 之前写过些简单介绍。
代码:
#include<iostream>
using namespace std;
const int INF=0x3fffffff;
int a[105], dp[105];
int main (void)
{
int n, ans = 0; cin>>n;
fill(dp, dp + n, INF);
for (int i = 0; i < n; i++){
cin>>a[i];
*lower_bound(dp, dp + n, a[i]) = a[i];
}
cout<<lower_bound(dp, dp +n, INF) - dp<<endl;
return 0;
}
最新文章
- linux lin命令
- git删除文件需要注意的事项
- python 获取启动参数
- 基于chrome内核的UXSS
- VCL自带的TabControl真心不好用...
- keil 编译的一些错误
- Oracle导入excel数据方法汇总[转]
- IOSi科研OS7 具体的使用说明的适应
- kafka删除topic的方法及我在kafka上边的一些经验
- 数据结构Java实现04---树及其相关操作
- 004_strace工具
- 10.C++-构造函数初始化列表、类const成员、对象构造顺序、析构函数
- A1083. List Grades
- python中logging模块使用
- Oracle EBS OM 登记订单
- Hbase之JAVA API不能远程访问问题解决
- 润乾报表JSF FORM 标签中使用填报表解决方案
- 【BZOJ2217】[Poi2011]Lollipop 乱搞
- Python之迭代器及生成器
- JQuery --- 第五期 (JQuery节点操作)