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

本文主要是介绍【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

样例输出

4
2
0

思路

首先，定义两个字符串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;
}