题目链接：https://www.acwing.com/problem/content/description/274/

两个序列 a,b 求最长公共上升子序列

我们定义f[i][j]  为  a序列的前i个和b序列的前j个元素的最长公共上升子序列
那么  当前的f[i][j] 可以继承 f[i-1][j] 的状态。如果a[i] == b[j] 那么它可能的状态是f[i-1][j]的状态，也有可能是f[i][1 ~ j - 1]中的某个状态+1。

这个应该很容易理解出来，复杂度为n^3

code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const int nn = 3010;
int f[nn][nn];
int n;
int a[nn],b[nn];
int main()
{
	n = read();
	for(int i=1;i<=n;i++)	a[i] = read();
	for(int i=1;i<=n;i++)	b[i] = read();
	
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	{
		f[i][j] = f[i-1][j];
		if(a[i]==b[j])
		{
			f[i][j] = max(1,f[i][j]);
			for(int k=1;k<j;k++)
				if(b[k]<b[j])
				{
					f[i][j] = max(f[i][j],f[i][k]+1);
				}
		}
	}
	int res = 0;
	for(int i=1;i<=n;i++) res = max(res,f[n][i]);
	cout<<res<<endl;
}

改进版：在上一个代码的情况下，我们发现  a[i]==b[j]的时候才会去考虑1 - j-1的状态，所以if(b[k]<b[j]) 可以 等价替换为 if(b[k]<a[i])
我们考虑  b[k]为  1~j-1的某个状态。而1~j-1是和第二层的循环顺序是一样的。而它的目的就是求1~j-1其中一个最优状态。所以我们在遍历二层循环的时候可以找一个变量记住每次最优状态。且当a[i] == b[j]时我们进行转移，最优状态的这个这个变量最少为1，因为每次相等时，这个状态至少为1.

code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const int nn = 3010;
int f[nn][nn];
int n;
int a[nn],b[nn];
int main()
{
	n = read();
	for(int i=1;i<=n;i++)	a[i] = read();
	for(int i=1;i<=n;i++)	b[i] = read();
	
	for(int i=1;i<=n;i++)
	{
		int tmax = 1;
		for(int j=1;j<=n;j++)
		{
			f[i][j] = f[i-1][j];
			if(a[i]==b[j]) f[i][j] = max(f[i][j],tmax);
			if(b[j]<a[i])
				tmax = max(f[i][j]+1,tmax);
		}
	}
	
	int res = 0;
	for(int i=1;i<=n;i++) res = max(res,f[n][i]);
	cout<<res<<endl;
}