将两个字符串打表可得到下述规律:


代码实现

根据上述的状态转移方程,我们可以写出代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5000;
string a, b;
int dp[maxn + 5][maxn + 5];
int main()
{
while(cin >> a >> b) {
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= a.size(); ++i) {
for(int j = 1; j <= b.size(); ++j) {
if(a[i - 1] == b[i - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
cout << dp[a.size()][b.size()] << endl;
}
return 0;
}


路径记录

上述代码只能得到最长的公共子序列长度,而不能输出最长公共子序列,为了得到最长公共子序列,我们对每一个状态的路径进行记录,再利用从后往前递推的方式,得到整个序列,而递归打印,可以帮助我们从后往前递推,但是从前往后打印的效果。

我们用0来标记两个字母相等的状态,1来表示该状态是从上方得到的,-1表示该状态从左方得到的,只有状态为0的时候,才打印字母。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5000;
int dp[maxn + 5][maxn + 5];
int vis[maxn + 5][maxn + 5]; // 0代表是从斜上方走下来的,1代表是从上方走过来的,-1代表是从左边走过来的
string a, b;
void printLCS(int i, int j)
{
if(i == 0 || j == 0) return;
if(!vis[i][j]) {
printLCS(i - 1, j - 1);
cout << a[i - 1];
}
else if(vis[i][j] == 1) printLCS(i - 1, j);
else
printLCS(i, j - 1);
}

int main()
{
while(cin >> a >> b) {
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= a.size(); ++i) {
for(int j = 1; j <= b.size(); ++j) {
if(a[i - 1] == b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
vis[i][j] = 0;
}
else if(dp[i - 1][j] > dp[i][j]) {
dp[i][j] = dp[i - 1][j];
vis[i][j] = 1;
}
else {
dp[i][j] = dp[i][j - 1];
vis[i][j] = -1;
}
}
}
cout <<dp[a.size()][b.size()] << endl;
printLCS(a.size(), b.size());
cout << endl;
}
}


代码优化

因为我们每次都只使用上一次的状态,那么完全可以不用nmn*m的二维数组,而改用2m2*m的一维数组来进行递推即可,这样大大降低了内存的使用,提高了效率。

写法一:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5000;
string a, b;
int dp[2][maxn + 5];
int main()
{
while(cin >> a >> b) {
memset(dp, 0, sizeof(dp));
int cur = 1, pre = 0;
for(int i = 1; i <= a.size(); ++i) {
for(int j = 1; j <= b.size(); ++j) {
if(a[i - 1] == b[j - 1])
dp[cur][j] = dp[pre][j - 1] + 1;
else
dp[cur][j] = max(dp[cur][j - 1], dp[pre][j]);
}
swap(cur, pre);
}
cout << dp[pre][b.size()] << endl; //因为当i = a.size()后,还进行了交换,所以此处是pre而不是cur
}
return 0;
}

写法二:

我们不用两个变量,而是采用取余或异或的方式来进行滚动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5000;
string a, b;
int dp[2][maxn + 5];
int main()
{
while(cin >> a >> b) {
memset(dp, 0, sizeof(dp));
int now = 1;
for(int i = 1; i <= a.size(); ++i) {
for(int j = 1; j <= b.size(); ++j) {
if(a[i - 1] == b[j - 1])
dp[now][j] = dp[now ^ 1][j - 1] + 1;
else
dp[now][j] = max(dp[now][j - 1], dp[now ^ 1][j]);
}
now ^= 1;
}
cout << dp[now ^ 1][b.size()] << endl; // 因为最后一步还做了异或运算,所以要再次异或还原
}
return 0;
}


进一步优化

让我们在看那段代码,在横向扫描并保存数组的时候,也起到了个滑动的功能。那我们能不能只有一个纵向的数组呢?
我们在更新数组时,会发现在更新时可能需要dp[pre][j]dp[pre][j]dp[cur][j1]dp[pre][j1]dp[cur][j-1] dp[pre][j-1]的值,实际上用一维数组dp[n]dp[n]即可。在将要更新dp[j]dp[j]前,dp[j]dp[j]值即是刚才dp[pre][j]dp[pre][j]的值,dp[cur][j1]dp[cur][j-1]的值对应现在dp[j1]dp[j-1]的值。 刚才dp[pre][j1]dp[pre][j-1]的值可以保存在一个临时变量prepre​中。

实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5000;
string a, b;
int dp[maxn + 5];
int main()
{
while(cin >> a >> b) {
memset(dp, 0, sizeof(dp));
int pre, tmp;
for(int i = 1; i <= a.size(); ++i) {
pre = dp[0]; // dp[0] 代表原来的 dp[i - 1][0]
for(int j = 1; j <= b.size(); ++j) {
tmp = dp[j]; // tmp代表dp[i - 1][j]的值
if(a[i - 1] == b[j - 1])
dp[j] = pre + 1; //代表dp[i - 1][j - 1] + 1;
else
dp[j] = max(dp[j - 1], dp[j]); //dp[i - 1] 代表 dp[i][j - 1]
pre = tmp;
}
}
cout << dp[b.size()] << endl;
}
return 0;
}

这样,我们把空间复杂度降为了O(n)O(n), 时间复杂度仍为O(nm)O(n * m)