注意是子序列而不是子数组（只要顺序对了匹配上了就行，可以不相邻）、
1先来看一道基础代码问题：
0最长公共子序列 – 蓝桥云课
示例 1
输入
5 6
1 2 3 4 5
2 3 2 1 4 5
输出
4
遇到这种题问题先想一想最笨的方法是啥：既然是求公共最长子序列，那么可以先固定上面的字符串，之后开始在第二个字符串中选所有可能的子序列，有点类似于一个集合有多少个子集合，每个元素有选和不选两种状态，并用一个path数组得到数组长度相同的子数组那么便可以通过dfs深度搜索出每一种情况之后进行比较，这种时间复杂度有点高，不过可以练一下基本功。
bool check(){
int n1=n,n2=path.size();
int cnt=0;
for(int i=0;i<n1;i++){
if(a[i]==path[i])
cnt++;
}
return cnt==n2;
}
void dfs(int pos)
{
// b 已经枚举完
if (pos > m)
{
if (check())
{
ans = max(ans, (int)path.size());
}
return;
}
// 情况1：不选 b[pos]
dfs(pos + 1);
// 情况2：选 b[pos]
path.push_back(b[pos]);
dfs(pos + 1);
// 回溯
path.pop_back();
}
这种做法的时间复杂度无疑是很高的，接下来讲正确解法：经典动态规划：
不妨设dp[i][j]是数组a前i个元素，b前j个元素的最长公共子序列大小，
接下来就要考虑状态转移方程，转移方程那肯定要从最后一位开始考虑了，对于最后一位总共有两种情况：第一种就是数组a第i位与数组b第j位一样，第二种情况就是不一样；
好了分别来看这两种情况：第一种情况就是在最后一位相同的情况下dp[i][j]，第二种情况就是最后一位不相同的情况下的dp[i][j]，接下来就是把限制条件给去掉
第一种情况：既然最后一位已经相同了，那边可以不再考虑了，dp[i][j]=dp[i-1]
[j-1]+1,即考虑倒数第二位的情况。
第二种情况下：已知必然存在最长公共子序列，那么最长公共子序列可能就是dp[i-1][j],dp[i][j-1]的最大值，我最后一位已经匹配不上了那不就是数组ab中最后一位的某一个没用吗？
#include<iostream>
using namespace std;
int a[1000],b[1000];
int dp[1000][1000];
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>a[i];
dp[i+1][0]=0;
}
for(int i=0;i<m;i++){
cin>>b[i];
dp[0][i+1]=0;
}
dp[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i-1]==b[j-1])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(dp[i][j]>ans)
ans=dp[i][j];
}
}
cout<<ans;
return 0;
}
这题是算大小那么如果题目要求输出这个最大子序列呢？
注意标准做法是有一个path数组记录dp数组的状态都是如何来的，方便查找
0查找最长的公共子序列 – 蓝桥云课
查找最长的公共子序列
题目描述
实现一个算法查找两个字符串最长的公共子字符串。子字符串的介绍如下：
- 子字符串是指字符串中任意个连续的字符组成的子序列。
输入描述
输入两行，每行一串字符串，长度均不超过 1000。
输出描述
输出一行，为最长公共子序列。
输入输出样例
示例
输入
ASDFGVCVMZKJ
OIKMASDFZCVM
输出
ASDF
#include <bits/stdc++.h>
using namespace std;
int dp[1001][1001];
int main()
{ string a,b;
cin>>a>>b;
int ans=0;
int n=a.size(),m=b.size();
int a1,b1;
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(a[i]==b[j]){
dp[i][j]=dp[i-1][j-1]+1;
if(ans<dp[i][j]){
ans=dp[i][j];
a1=i,b1=j;
}
}
else{
dp[i][j]=0;
}
}
}
string ans1;
while(a1>=0&&b1>=0&&a[a1]==b[b1]){
ans1+=a[a1];
a1–;
b1–;
}
reverse(ans1.begin(),ans1.end());
cout<<ans1;
return 0;
}
笔者这里并没选择标准做法做法，动态数组状态的定义也有些许不同，dp[i][j]代表的是以数组a第i个元素数组b第j个元素结尾的子字符串的长度，下面来看标准做法
#include <bits/stdc++.h>
using namespace std;
int dp[1001][1001];
int path[1001][1001];
string a,b;
void dfs(string &ans , int n , int m ){
if(n==0||m==0)
return ;
if(path[n][m]==1){
dfs(ans,n-1,m);
return;
}
if(path[n][m]==2){
dfs(ans,n,m-1);
return ;
}
if(path[n][m]==3){
ans+=a[n-1];
dfs(ans,n-1,m-1);
return;
}
}
int main()
{
cin>>a>>b;
int n=a.size(),m=b.size();
for(int i=0;i<=n;i++){
dp[0][i]=0;
}
for(int i=0;i<=m;i++){
dp[i][0]=0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i-1]==b[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
path[i][j]=3;
}
else{
dp[i][j]=0;
if(dp[i-1][j]>dp[i][j-1]){
path[i][j]=1;
}
else{
path[i][j]=2;
}
}
}
}
int t=0;
int l=0,r=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
//cout<<path[i][j]<<" ";
if(t<dp[i][j]){
t=dp[i][j];
l=i,r=j;
}
}
//cout<<endl;
}
string ans;
dfs(ans,l,r);
reverse(ans.begin(),ans.end());
cout<<ans;
return 0;
}
这里path数组的作用是用来辅助完善dp数组的，记录最长子序列的来时道路。
不对不对：这个dfs的停止位置根本不对！！！甚至这个path数组都不对
X1ASDF X23ASDF
这组数据就能证明标准做法的代码是错误的，同时根据dp数组的定义：dp[i][j]代表的是以数组a第i个元素数组b第j个元素结尾的子字符串的长度，便可以倒推出来：
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(a[i]==b[j]){
dp[i][j]=dp[i-1][j-1]+1;
if(ans<dp[i][j]){
ans=dp[i][j];
a1=i,b1=j;
}
}
else{
dp[i][j]=0;
}
}
}
string ans1;
while(a1>=0&&b1>=0&&a[a1]==b[b1]){
ans1+=a[a1];
a1–;
b1–;
}
