注意是子序列而不是子数组只要顺序对了匹配上了就行可以不相邻、1先来看一道基础代码问题0最长公共子序列 - 蓝桥云课示例 1输入5 6 1 2 3 4 5 2 3 2 1 4 5输出4遇到这种题问题先想一想最笨的方法是啥既然是求公共最长子序列那么可以先固定上面的字符串之后开始在第二个字符串中选所有可能的子序列有点类似于一个集合有多少个子集合每个元素有选和不选两种状态并用一个path数组得到数组长度相同的子数组那么便可以通过dfs深度搜索出每一种情况之后进行比较这种时间复杂度有点高不过可以练一下基本功。bool check(){ int n1n,n2path.size(); int cnt0; for(int i0;in1;i){ if(a[i]path[i]) cnt; } return cntn2; } 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中最后一位的某一个没用吗#includeiostream using namespace std; int a[1000],b[1000]; int dp[1000][1000]; int main(){ int n,m; cinnm; for(int i0;in;i){ cina[i]; dp[i1][0]0; } for(int i0;im;i){ cinb[i]; dp[0][i1]0; } dp[0][0]0; for(int i1;in;i){ for(int j1;jm;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 ans0; for(int i1;in;i){ for(int j1;jm;j){ if(dp[i][j]ans) ansdp[i][j]; } } coutans; 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; cinab; int ans0; int na.size(),mb.size(); int a1,b1; for(int i0;in;i){ for(int j0;jm;j){ if(a[i]b[j]){ dp[i][j]dp[i-1][j-1]1; if(ansdp[i][j]){ ansdp[i][j]; a1i,b1j; } } else{ dp[i][j]0; } } } string ans1; while(a10b10a[a1]b[b1]){ ans1a[a1]; a1--; b1--; } reverse(ans1.begin(),ans1.end()); coutans1; 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(n0||m0) 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){ ansa[n-1]; dfs(ans,n-1,m-1); return; } } int main() { cinab; int na.size(),mb.size(); for(int i0;in;i){ dp[0][i]0; } for(int i0;im;i){ dp[i][0]0; } for(int i1;in;i){ for(int j1;jm;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 t0; int l0,r0; for(int i1;in;i){ for(int j1;jm;j){ //coutpath[i][j] ; if(tdp[i][j]){ tdp[i][j]; li,rj; } } //coutendl; } string ans; dfs(ans,l,r); reverse(ans.begin(),ans.end()); coutans; return 0; }这里path数组的作用是用来辅助完善dp数组的记录最长子序列的来时道路。不对不对这个dfs的停止位置根本不对甚至这个path数组都不对X1ASDFX23ASDF这组数据就能证明标准做法的代码是错误的同时根据dp数组的定义dp[i][j]代表的是以数组a第i个元素数组b第j个元素结尾的子字符串的长度便可以倒推出来for(int i0;in;i){ for(int j0;jm;j){ if(a[i]b[j]){ dp[i][j]dp[i-1][j-1]1; if(ansdp[i][j]){ ansdp[i][j]; a1i,b1j; } } else{ dp[i][j]0; } } } string ans1; while(a10b10a[a1]b[b1]){ ans1a[a1]; a1--; b1--; }