正规题解（1e5数据范围可过）

这道题测试点太水，提交记录有人开大小1000的都过了。

思路

状态定义：dp[j] = 以 b[j] 结尾的最长公共子序列长度。
状态转移：a[i] = b[j] 时： dp[j] = 之前最大的公共子序列长度 + 1（当前元素）

一维优化的核心是：用 dp[j] 替代 dp[i-1][j]（上一轮的结果），而 dp[i][j-1] 可以通过遍历过程中记录的最大值（即now）来表示。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N=1e5;
int n,a[N+10],b[N+10],dp[N+10],ans;

int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	
	for(int i=1;i<=n;i++){
		int now=0;
		for(int j=1;j<=n;j++){
			now=max(now,dp[j]); //now=当前的公共子序列最大长度
			if(a[i]==b[j]) dp[j]=now+1;
		}
	}
	
	for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
	
    cout<<ans;
    
	return 0;
}