线性dp(lis)学习笔记

By Jeffery

第一步：读懂题目(包括对象，已知条件，所求内容)

已知:一个长度为n的队列

所求:${\color{Red}最长上升子序列}$的${\color{Red}长度}$(可间断)

第二步:分析:怎么求，用什么算法求解(算法分析)

由于本题为最长上升子序列(lis)的模板题，所以我们显而易见地知道本题应该使用线性dp。

线性dp是在线性结构上进行状态转移,它除了在最本题(最长上升子序)列及其类似问题(如:最长不上升子序列等)之外,一般没有固定模板。

本题的dp六要素(50分):

阶段 子序列的末尾的节点编号

状态 $j$开始到$i$的子序列(不一定连续)

决策 选择或不选择接上其他子序列

状态转移方程 dp[i]=max(dp[i],dp[j]+1);

初始值 dp[i]=1 ($1$<=$i$<=$n$)

目标值 max{dp[i]} ($1$<=$i$<=$n$)

本题的dp六要素(100分,lower_bound优化):

阶段 上升子序列的长度

状态 遍历到第i个

决策 (无)

状态转移方程

if(dp[ans]<a[i])
{
	ans++;
	dp[ans]=a[i];
}
else
{
	*(lower_bound(dp+1,dp+1+ans,a[i]))=a[i];//使用lower_bound进行查找
}

初始值 dp[1]=a[1]

目标值 ans

第三步：分析该算法的核心代码

50分

for(int i=1;i<=n;i++)
{
	for(int j=0;j<i;++j)
	{
		if(a[i]>a[j])dp[i]=max(dp[i],dp[j]+1);
	}
}

100分,lower_bound优化

for(int i=2;i<=n;++i)
{
	if(dp[ans]<a[i])
	{
		ans++;
		dp[ans]=a[i];
	}
	else
	{
		*(lower_bound(dp+1,dp+1+ans,a[i]))=a[i];//使用lower_bound进行查找
	}
}

第四步：代码呈现

50分

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MAX 200001
using namespace std;
int n,a[MAX],dp[MAX];//dp[i]表示第i个数结尾的子序列
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		dp[i]=1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<i;++j)
		{
			if(a[i]>a[j])dp[i]=max(dp[i],dp[j]+1);
		}
	}
	int ans=1;
	for(int i=1;i<=n;i++)if(dp[i]>ans)ans=dp[i];
	printf("%d",ans);
    return 0;
}

100分,lower_bound优化

#include <iostream>
#include <cstring>
#include <cmath>
#include <climits>
#include <algorithm>
#define MAX 200001
using namespace std;
int n,ans=1,a[MAX],dp[MAX];//dp[i]表示长度为i的上升子序列的末尾的数字
int main()
{

	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
	}
	dp[1]=a[1];
	for(int i=2;i<=n;++i)
	{
		if(dp[ans]<a[i])
		{
			ans++;
			dp[ans]=a[i];
		}
		else
		{
			*(lower_bound(dp+1,dp+1+ans,a[i]))=a[i];//使用lower_bound进行查找
		}
	}
	printf("%d",ans);
	return 0;
}