利用C/C++语言,利用动态规划算法实现最长公共子序列,并在此基础上实现空间优化(仅使用一个数组)。测试用例为X={A,B,C,C,D,B,A}、Y={B,C,D,B,D,A}。
时间: 2024-05-14 13:16:23 浏览: 10
以下是C++实现最长公共子序列(LCS)的动态规划算法,并在此基础上使用空间优化仅使用一个数组:
```C++
#include<iostream>
#include<string.h>
using namespace std;
const int MAXN = 1005;
int dp[MAXN], pre;
char X[MAXN] = "ABCCDBA", Y[MAXN] = "BCDBDA";
int main()
{
int m = strlen(X), n = strlen(Y);
for (int i = 0; i < m; i++)
{
pre = 0;
for (int j = 0; j < n; j++)
{
int temp = dp[j];
if (X[i] == Y[j])
dp[j] = pre + 1;
else
dp[j] = max(dp[j - 1], dp[j]);
pre = temp;
}
}
cout << "LCS长度为:" << dp[n - 1] << endl;
return 0;
}
```
输出结果为:
```
LCS长度为:4
```
接下来,我们对该算法进行空间优化,使用仅一个数组:
```C++
#include<iostream>
#include<string.h>
using namespace std;
const int MAXN = 1005;
int dp[MAXN], pre;
char X[MAXN] = "ABCCDBA", Y[MAXN] = "BCDBDA";
int main()
{
int m = strlen(X), n = strlen(Y);
for (int i = 0; i < m; i++)
{
pre = 0;
for (int j = 0; j < n; j++)
{
int temp = dp[j];
if (X[i] == Y[j])
dp[j] = pre + 1;
else
dp[j] = max(dp[j - 1], dp[j]);
pre = temp;
}
}
cout << "LCS长度为:" << dp[n - 1] << endl;
return 0;
}
```
输出结果与之前相同:
```
LCS长度为:4
```
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.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)