最长公共子序列动态规划算法
时间: 2023-09-11 14:03:57 浏览: 71
最长公共子序列(Longest Common Subsequence,简称 LCS)是指两个或多个字符串中最长的公共子序列。动态规划算法是求解 LCS 问题的一种有效方法。
具体来说,对于两个字符串 S1 和 S2,定义一个二维数组 dp,其中 dp[i][j] 表示 S1 的前 i 个字符和 S2 的前 j 个字符的最长公共子序列长度。则有以下递推公式:
- 当 S1[i-1] = S2[j-1] 时,dp[i][j] = dp[i-1][j-1] + 1;
- 当 S1[i-1] != S2[j-1] 时,dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
其中,第一种情况表示当前两个字符相同,所以最长公共子序列长度加一;第二种情况表示当前两个字符不同,所以最长公共子序列长度不变,需要在 dp[i-1][j] 和 dp[i][j-1] 中取最大值。
最后,dp[m][n] 就是 S1 和 S2 的最长公共子序列长度,其中 m 和 n 分别为 S1 和 S2 的长度。
可以使用两个指针 i 和 j,从 dp[m][n] 开始,根据 dp 数组的值逆推出最长公共子序列。具体来说,如果 S1[i-1] = S2[j-1],则该字符属于最长公共子序列,将其加入结果序列,并向左上方移动指针;否则,如果 dp[i-1][j] > dp[i][j-1],则向上移动指针;如果 dp[i-1][j] < dp[i][j-1],则向左移动指针。重复以上步骤,直到指针移动到 dp[0][0] 位置,即找到了最长公共子序列。
相关问题
最长公共子序列动态规划算法c++
以下是最长公共子序列的动态规划算法的 C++ 代码实现:
```c++
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 1005;
int dp[MAXN][MAXN];
int main() {
string s1, s2;
cin >> s1 >> s2;
int n = s1.length(), m = s2.length();
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
cout << dp[n][m] << endl;
return 0;
}
```
其中,`dp[i][j]` 表示 s1 的前 i 个字符和 s2 的前 j 个字符的最长公共子序列的长度。在状态转移时,如果两个字符相等,那么最长公共子序列的长度就是它们前面的最长公共子序列长度再加 1;否则,最长公共子序列的长度就是 s1 前 i - 1 个字符和 s2 前 j 个字符的最长公共子序列长度和 s1 前 i 个字符和 s2 前 j - 1 个字符的最长公共子序列长度的最大值。最终,`dp[n][m]` 就是 s1 和 s2 的最长公共子序列的长度。
最长公共子序列动态规划算法c语言
最长公共子序列是指在两个序列中,找到一个最长的子序列,使得它在两个序列中的相对位置都相同。下面是使用动态规划算法求解最长公共子序列的C语言代码:
```c
#include <stdio.h>
#include <string.h>
#define MAXLEN 100 //最大序列长度
int dp[MAXLEN][MAXLEN]; //记录最长公共子序列的长度
int LCS(char *str1, char *str2, int len1, int len2)
{
int i, j;
//初始化第一行和第一列
for (i = 0; i <= len1; i++)
dp[i][0] = 0;
for (j = 0; j <= len2; j++)
dp[0][j] = 0;
//动态规划求解
for (i = 1; i <= len1; i++)
{
for (j = 1; j <= len2; j++)
{
if (str1[i-1] == str2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = (dp[i][j-1] > dp[i-1][j]) ? dp[i][j-1] : dp[i-1][j];
}
}
//返回最长公共子序列的长度
return dp[len1][len2];
}
int main()
{
char str1[MAXLEN], str2[MAXLEN];
int len1, len2, lcs_len;
//读入两个字符串
printf("请输入第一个字符串:");
gets(str1);
printf("请输入第二个字符串:");
gets(str2);
//计算最长公共子序列的长度
len1 = strlen(str1);
len2 = strlen(str2);
lcs_len = LCS(str1, str2, len1, len2);
//输出结果
printf("最长公共子序列的长度为:%d\n", lcs_len);
return 0;
}
```
其中,dp[i][j]表示str1的前i个字符和str2的前j个字符的最长公共子序列的长度。在动态规划求解时,如果str1[i-1]等于str2[j-1],则当前字符可以加入最长公共子序列中,此时dp[i][j]等于dp[i-1][j-1]+1;否则,当前字符不能加入最长公共子序列中,此时dp[i][j]等于dp[i][j-1]和dp[i-1][j]中的较大值。最终,dp[len1][len2]即为最长公共子序列的长度。
相关推荐
![](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)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)