1.LCS 算法模型

LCS 问题就是给定两个序列 A 和 B，求他们最长的公共子序列。

在求解时，我们会设 dp[i][j]表示为 A[1 ~ i]序列和 B[1 ~ j]序列中（不规定结尾）的最长子序列的长度。

if(a[i]==b[i]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

就是说，当 a[i]=b[j]时，可以将他们作为插入到 LCS 的后面，长度加 1 即可；当 a[i]!=b[j]时，说明此时 LCS 不会延长，那么就要从 dp[i-1][j]和 dp[i][j-1]中取大的作为最长的长度。

示例代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e3+5;
int n,m;
ll a[N],b[N],dp[N][N];
int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int j=1;j<=m;j++)cin>>b[j];

	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i]==b[j])dp[i][j]=dp[i-1][j-1]+1;
			else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}
	cout<<dp[n][m];
	return 0;
}

如何求出具体的最长子序列？

	vector<int> v;
	int x=n,y=m;
	// 只需要从dp[n][m]向前搜索即可，如果相等则回到左上方，否则回到max(上边，左边)
	while(x&&y){
		if(a[x]==b[y]){
			v.push_back(a[x]);
			x--,y--;//左上走
		}else if(dp[x-1][y]>dp[x][y-1])x--;//向大的走
		else y--;
	}
	reverse(v.begin(),v.end());
	for(const auto &i:v)cout<<i<<' ';

2.LIS 算法模型

最长上升子序列是一个经典的 DP 模型。

子序列指的是一个序列中，按照原顺序选出若干个不一定连续的元素所组成的序列。

在求解 LIS 时，一般我们会设 dp[i]表示 1~i 序列中以 a[i]结尾的最长上升子序列的长度。

状态转移方程为：dp[i] = max(dp[i],dp[j] + 1),if a[i] > a[j]

表示 a[i]要插入到不同的子序列后面的情况。

模板例题：

// 设状态 dp[i]表示1~i的最长上升子序列的长度，状态转移方程为 dp[i]=max(dp[i],dp[j]+1) if a[i]>a[j]
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
using ll = long long;
const int N = 5e5+10;
int dp[N];
ll n,a[N];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	// 算法优化，实现O(nlogn)
	// 如果后边有比较小的值的话，只进行更新数值，虽然前面已经形成的子序列被改变，当时它的长度是没变的，也就是说不断更新数值，最后在容器后边加上符合要求的值
	vector<int> v;
	for(int i=1;i<=n;i++){
		if(v.empty()||a[i]>v.back()){
			v.push_back(a[i]);
		}else{
			auto it=lower_bound(v.begin(),v.end(),a[i]);
			*it=a[i];
		}
	}
	cout<<v.size();
	return 0;
}