2524: 最长公共子序列c++
时间: 2023-10-14 17:04:37 浏览: 49
最长公共子序列(Longest Common Subsequence)是指给定两个序列,找出在两个序列中都存在的最长子序列的长度。
以下是一个用 C++ 实现最长公共子序列的示例代码:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
int longestCommonSubsequence(std::string text1, std::string text2) {
int m = text1.length();
int n = text2.length();
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
int main() {
std::string text1 = "ABCBDAB";