算法1
C++ 代码
///////最长公共子序列--------LCS-----模板
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, a[1111], b[1111], f[1111][1111];///从1~i和1~j分别a[i]和b[j]相同的序列长度
int main(){
cin >> n >> m;
for(int i = 1; i <= n; ++ i) cin >> a[i];
for(int i = 1; i <= m; ++ i) cin >> b[i];
for(int i = 1; i <= n; ++ i){
for(int j = 1; j <= m; ++ j){
if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);///不选,选
else if(a[i] != b[i]) f[i][j] = max(f[i - 1][j], f[i][j - 1]);///转移从上,从左
}
}
cout << f[n][m] << '\n';
//-------------------------------分割线------------------------------------------------------
//求出具体的最长公共子序列
vector<int> v;
int x = n, y = m;
while(x && y){/////在地图内时..
if(a[x] == b[y]){
v.push_back(a[x]);
x --, y --; /// 相等一定是从左上角方向转移过来的
}
else if(f[x-1][y] > f[x][y-1]) x --; /// 否则就(从左)或(从上)选择一个较大的方向去
else y --;
}
reverse(v.begin(), v.end());
for(const auto i : v)
cout << i << ' ';
system("pause");
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla