取出序列中某些特定的项并保持它们在原来序列中的顺序,所得到的新序列成为原序列的子序列。
(所以说,子序列未必是连续的,连续的就叫子集了)
#include <iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX_N = 1000, MAX_M = 1000;
//输入
int n, m;
char s[MAX_N], t[MAX_M];
int dp[MAX_N + 1][MAX_M + 1];//DP数组
void solve()
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (s[i] == t[j])
{
dp[i + 1][j + 1] = dp[i][j] + 1;
}
else
{
dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
}
}
}
cout << dp[n][m] << endl;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> s[i];
}
for (int i = 0; i < n; i++)
{
cin >> t[i];
}
memset(dp, 0, sizeof(dp));
solve();
return 0;
}