目录
牛客_最长公共子序列(dp模板)
解析代码
子序列即两个字符串中公共的 字符,但不一定连续。
从题干中可以提取出问题:求字符串s和t的最长公共子序列 假设LCS(m,n)为长度为m的字符串s与长度为n的字符串t的最长公共子序列,直接进行求解时不太 好求解,那么可以将问题简化为其子问题,假设s和t的长度为任意值i和j,即求LCS(i,j):
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int LCS(const string& m, const string& n)
{ // Longest common subsequence
int n1 = m.size(), n2 = n.size();
vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));
for (int i = 1; i <= n1; ++i)
{
for (int j = 1; j <= n2; ++j)
{
if (m[i - 1] == n[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[n1][n2];
}
int main()
{
string m, n;
while (cin >> m >> n)
{
cout << LCS(m, n) << endl;
}
return 0;
}
标签:OJ,int,牛客,公共,序列,最长,dp
From: https://blog.csdn.net/GRrtx/article/details/141818766