【ETOJ P1025】最长公共子序列 题解（动态规划+最长公共子序列）

题目描述

给你一个序列 $X$ 和另一个序列 $Z$，当 $Z$ 中的所有元素都在 $X$ 中存在，并且在 $X$ 中的下标顺序是严格递增的，那么就把 $Z$ 叫做 $X$ 的子序列。

例如：$Z=<a,b,f,c>$ 是序列 $X=<a,b,c,f,b,c>$ 的一个子序列， $Z$ 中的元素在 $X$ 中的下标序列为 $<1,2,4,6>$。

现给你两个序列 $X$ 和 $Y$，请问它们的最长公共子序列的长度是多少？

输入

输入包含多组测试数据。每组输入占一行，为两个字符串，由若干个空格分隔。每个字符串的长度不超过 100。

输出

对于每组输入，输出两个字符串的最长公共子序列的长度。

样例输入

abcfbc abfcab
programming contest 
abcd mnp
1
2
3

样例输出

4
2
0
1
2
3

---

思路

首先，定义两个字符串s1和s2，以及一个二维数组dp，用于存储动态规划的状态。

然后，通过一个无限循环，持续从输入流中读取两个字符串。对于每一对输入的字符串，获取它们的长度l1和l2，然后在字符串前加上一个空格，使得字符串的索引从1开始，这样方便后续的动态规划过程。

接着，初始化动态规划数组dp为全0。然后，开始动态规划的过程。遍历字符串s1和s2的每一个字符，如果两个字符相等，那么dp[i][j]就等于dp[i-1][j-1]+1；否则，dp[i][j]就等于dp[i-1][j]和dp[i][j-1]中的较大值。

最后，输出dp[l1][l2]，即两个字符串的最长公共子序列的长度。

注意：在读取两个字符串后，要在每个字符串的头部插入一个空格，使字符串的索引从1开始，而不是从0开始。否则，在动态规划的循环过程中，当i或j为0时，dp[i-1][j-1]会变成dp[-1][-1]，数组越界导致程序错误。

---

AC代码

#include <cstring>
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;

const int N = 1e2 + 7;

string s1, s2;
int dp[N][N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	while (cin >> s1 >> s2) {
		int l1 = s1.length();
		int l2 = s2.length();
		s1 = " " + s1;
		s2 = " " + s2;
		memset(dp, 0, sizeof(dp));
		for (int i = 1; i <= l1; i++) {
			for (int j = 1; j <= l2; j++) {
				if (s1[i] == s2[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[l1][l2] << endl;
	}
	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
26
27
28
29
30
31
32
33
34
35