求两个数列的最长公共子序列长度 c++完整代码
时间: 2024-10-04 13:03:02 浏览: 2
求两个数列的最长公共子序列(Longest Common Subsequence,LCS)通常使用动态规划的方法解决,下面是一个简单的C++实现,使用二维数组记录中间状态:
```cpp
#include <iostream>
#include <vector>
int lcs(std::vector<int>& nums1, std::vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
// 创建一个二维数组,初始化为0
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) {
// 如果当前元素相等,那么最长公共子序列长度就是前一个元素加上1
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
// 如果不相等,选择两个数列中的最大值作为当前的LCS长度
else {
dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n]; // 返回最后的结果即LCS长度
}
int main() {
std::vector<int> nums1 = {1, 2, 3, 4, 5};
std::vector<int> nums2 = {6, 7, 8, 9, 5};
int result = lcs(nums1, nums2);
std::cout << "The length of the longest common subsequence is: " << result << std::endl;
return 0;
}
```