Dynamic programming -- linear DP

1. Longest ascending subsequence （LIS）  

 Plain writing   n^2
for(int i=1;i<=n;i++)
{
	f[i]=1;
	for(int j=1;j<i;j++)
		if(a[i]>a[j])
			f[i]=max(f[i],f[j]+1);
}
int m=0;
for(int i=1;i<=n;i++) m=max(m,f[i]);

 Binary optimization   nlogn
int f[N];// The length is i The last bit of the increasing subsequence of  
int LIS()
{
	int len=0;
	f[0]=-0x3f3f3f3f;
	for(int i=1;i<=n;i++)
	{
		int l=0,r=len;
		while(l<r)// Find less than a[i] The last number of  
		{
			int mid=l+r+1>>1;
			if(f[mid]<a[i])
				l=mid;
			else
				r=mid-1;
		}
		len=max(len,r+1);
		f[r+1]=a[i];
	}
	return len;
}

2. Longest common subsequence （LCS）   

//LCS    o(n^2)
int f[N][N];// Before the first sequence i Letters and the first of the second sequence j A subsequence of letters   Maximum common subsequence length of