文章目录
895.最长公共子序列
题目描述
给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数 N 和 M。
第二行包含一个长度为 N 的字符串，表示字符串 A。
第三行包含一个长度为 M 的字符串，表示字符串 B。
字符串均由小写字母构成。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N,M≤1000
输入样例：
4 5
acbd
abedc
输出样例：
3
动态规划
代码实现了计算两个字符串最长公共子序列（Longest Common Subsequence, LCS）的长度。
// 引入所有标准库
#include<bits/stdc++.h>
using namespace std;
// 定义dp数组，用来保存到当前位置为止的最长公共子序列的长度
int dp[1010][1010];
// 定义两个字符数组存放输入的字符串
char a[1010],b[1010];
// 定义n和m分别为字符串A和B的长度
int n,m;
int main()
{
// 读入字符串的长度
cin>>n>>m;
// 读入两个字符串，存储在字符数组a和b中，从索引1开始存储以方便后面计算
scanf("%s",a+1);
scanf("%s",b+1);
// 循环遍历字符串a和b
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
// 计算dp[i][j]，也就是到a的第i个字符和b的第j个字符为止的最长公共子序列
// 首先，取不包含a[i]和b[j]的子序列的较大者
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
// 如果当前两个字符相同，则考虑将这个字符加入到子序列中
if(a[i]==b[j])
// 更新dp[i][j]，因为找到了一个公共字符，所以取dp[i-1][j-1]加1与当前dp[i][j]的较大者
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
}
}
// 输出最终的最长公共子序列的长度，即dp[n][m]
cout<<dp[n][m];
return 0;
}
上述代码使用了二维动态规划的方法来解决问题。dp[i][j]代表考虑字符串A的前i个字符和字符串B的前j个字符时，最长公共子序列的长度。通过比较字符串A的第i个字符和B的第j个字符，我们可以更新dp[i][j]的值。如果A的第i个字符和B的第j个字符相同，这个字符一定在最长公共子序列中，因此dp[i][j]至少应该是dp[i-1][j-1] + 1。我们遍历所有的位置，最终dp[n][m]就是答案。