最长公共子序列问题的算法C++代码
时间: 2024-10-18 10:13:33 浏览: 26
最长公共子序列问题 动态规划法.cpp.rar
5星 · 资源好评率100%
最长公共子序列(Longest Common Subsequence, LCS)问题是计算机科学中的一种经典动态规划问题。它的目标是在两个序列中找到具有最大长度的共同子序列,但子序列并不一定连续。下面是一个简单的C++代码示例,用于解决这个问题:
```cpp
#include <iostream>
#include <vector>
std::string lcs(std::string str1, std::string str2) {
int m = str1.length();
int n = str2.length();
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (str1[i - 1] == str2[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]);
}
}
}
// Build the LCS string by backtracking
std::string result;
int i = m, j = n;
while (i > 0 && j > 0) {
if (str1[i - 1] == str2[j - 1]) {
result = str1[i - 1] + result;
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return result;
}
int main() {
std::string s1 = "ABCDGH";
std::string s2 = "AEDFHR";
std::cout << "LCS of " << s1 << " and " << s2 << " is: " << lcs(s1, s2) << std::endl;
return 0;
}
```
这个代码首先初始化了一个二维动态规划数组`dp`,然后通过两层循环计算出每个位置的最长公共子序列长度。最后回溯`dp`数组构建最长公共子序列。
阅读全文