2. 最长公共子序列 对于两个字符串,请设计一个高效算法,求他们的最长公共子序列的长度,这里的最长公共子序列定义为有两个序列U1,U2,U3...Un和V1,V2,V3...Vn,其中Ui<Ui+1,Vi<Vi+1。且A[Ui] == B[Vi]。 给定两个字符串A和B,同时给定两个串的长度n和m,请返回最长公共子序列的长度。保证两串长度均小于等于300。 测试样例: "1A2C3D4B56",10,"B1D23CA45B6A",12
时间: 2024-02-27 21:54:38 浏览: 53
以下是求解最长公共子序列长度的 C++ 代码,使用了动态规划的思想:
```c++
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int LCSLength(string A, int n, string B, int m) {
vector<vector<int>> C(n+1, vector<int>(m+1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (A[i-1] == B[j-1]) {
C[i][j] = C[i-1][j-1] + 1;
} else {
C[i][j] = max(C[i][j-1], C[i-1][j]);
}
}
}
return C[n][m];
}
int main() {
string A = "1A2C3D4B56";
string B = "B1D23CA45B6A";
int n = A.size();
int m = B.size();
int lcs = LCSLength(A, n, B, m);
cout << "LCS length: " << lcs << endl;
return 0;
}
```
程序输出的结果为 6,表示这两个字符串的最长公共子序列长度为 6。你可以使用该代码来解决你的问题。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)