需要用算法设计与分析书中的内容写全部代码
时间: 2024-03-05 10:52:07 浏览: 17
好的,以下是最长公共子序列的C++代码(使用动态规划):
```cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
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] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
int main() {
string s1 = "abcde";
string s2 = "ace";
int result = longestCommonSubsequence(s1, s2);
cout << result << endl;
return 0;
}
```
这段代码的时间复杂度为$O(mn)$,其中$m$和$n$分别是两个字符串的长度。具体来说,我们定义了一个二维数组`dp`,其中`dp[i][j]`表示`s1`的前$i$个字符和`s2`的前$j$个字符的最长公共子序列的长度。初始化时,将所有的`dp[i][0]`和``dp[0][j]`都设置为0,表示空串的最长公共子序列长度为0。接下来,对于每个$i$和$j$,我们进行如下判断:
- 如果`s1[i-1]`等于`s2[j-1]`,那么`s1`的前$i$个字符和`s2`的前$j$个字符的最长公共子序列,就是`s1`的前$i-1$个字符和`s2`的前$j-1$个字符的最长公共子序列,再加上一个`s1[i-1]`。也就是说,此时`dp[i][j]`等于`dp[i-1][j-1]`加1。
- 如果`s1[i-1]`不等于`s2[j-1]`,那么`s1`的前$i$个字符和`s2`的前$j$个字符的最长公共子序列,就是分别考虑`s1`的前$i-1$个字符和`s2`的前$j$个字符,以及`s1`的前$i$个字符和`s2`的前$j-1$`个字符的最长公共子序列,取它们的最大值。也就是说,此时`dp[i][j]`等于`max(dp[i-1][j], dp[i][j-1])`。
最后,`dp[m][n]`就是`s1`和`s2`的最长公共子序列的长度。