最长公共子序列最优解和最优值
时间: 2023-08-06 08:02:34 浏览: 47
最长公共子序列(Longest Common Subsequence,简称LCS)问题是指:给定两个序列X和Y,求它们的最长公共子序列,即在X和Y中找到一个最长的公共子序列。
最优解:最长公共子序列问题可以使用动态规划求解,其时间复杂度为O(mn),其中m和n分别为两个输入序列的长度。使用动态规划时,可以使用一个二维数组dp[i][j]表示序列X[0:i]和序列Y[0:j]的最长公共子序列的长度。根据LCS的定义,可以得到以下状态转移方程:
如果X[i] == Y[j],则dp[i][j] = dp[i-1][j-1] + 1;
如果X[i] != Y[j],则dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
最优值:最长公共子序列问题的最优值即为两个序列的最长公共子序列的长度,即dp[m][n]。
相关问题
C语言用自底向上方式求解最长公共子序列问题,给出最优值和最优解
最长公共子序列问题可以用动态规划求解,其中自底向上方式是一种较为常见的实现方式。
假设有两个序列A和B,长度分别为m和n,对应的序列为a和b。定义dp[i][j]表示以a[i]和b[j]结尾的最长公共子序列的长度。
动态规划的基本思想是将一个大问题拆分成若干个子问题进行求解,并将子问题的解组合起来得到原问题的解。在本问题中,每个dp[i][j]都依赖于dp[i-1][j-1]、dp[i-1][j]和dp[i][j-1]的值,而dp[i-1][j-1]、dp[i-1][j]和dp[i][j-1]又可以通过已知的dp值来求解。
具体地,当a[i]等于b[j]时,dp[i][j] = dp[i-1][j-1] + 1,因为此时a[i]和b[j]可以组成一个新的公共子序列;否则,dp[i][j] = max(dp[i-1][j], dp[i][j-1]),因为此时a[i]和b[j]不能构成公共子序列,需要从dp[i-1][j]和dp[i][j-1]中选取较大的一个。
最优解即为最长公共子序列,可以通过回溯求解得到。具体地,从dp[m][n]开始,如果a[i]等于b[j],则该字符属于最长公共子序列,将该字符加入答案中,并向左上角移动一步;否则,如果dp[i-1][j]大于dp[i][j-1],则向上移动一步;否则,向左移动一步。重复上述过程直到dp[0][0]为止。
下面是C语言的实现代码:
```c
#include <stdio.h>
#include <string.h>
#define MAX_LEN 100
int dp[MAX_LEN][MAX_LEN]; // dp数组
char a[MAX_LEN], b[MAX_LEN]; // 输入的两个序列
char ans[MAX_LEN]; // 最长公共子序列
int main() {
scanf("%s %s", a, b);
int m = strlen(a), n = strlen(b);
// 初始化dp数组
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a[i-1] == b[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
}
}
}
printf("最长公共子序列的长度为:%d\n", dp[m][n]);
// 回溯求解最长公共子序列
int i = m, j = n, k = dp[m][n] - 1;
while (i > 0 && j > 0) {
if (a[i-1] == b[j-1]) {
ans[k--] = a[i-1];
i--;
j--;
} else if (dp[i-1][j] > dp[i][j-1]) {
i--;
} else {
j--;
}
}
printf("最长公共子序列为:%s\n", ans);
return 0;
}
```
输入样例:
```
ABCBDAB
BDCABA
```
输出样例:
```
最长公共子序列的长度为:4
最长公共子序列为:BCBA
```
C语言求解最长公共子序列问题,给出最优值和最优解,并且通过实例验证:用自底向上方式求解
最长公共子序列问题是指给定两个序列,找到它们之间最长的公共子序列。可以使用动态规划来解决该问题。
具体来说,设两个序列分别为 $A=a_1,a_2,\cdots,a_m$ 和 $B=b_1,b_2,\cdots,b_n$,定义 $L(i,j)$ 为 $A$ 的前 $i$ 个元素和 $B$ 的前 $j$ 个元素的最长公共子序列长度,则可以得到以下递推式:
$$
L(i,j)=\begin{cases}
0 & i=0 \text{ 或 } j=0 \\
L(i-1,j-1)+1 & a_i=b_j \\
\max(L(i-1,j),L(i,j-1)) & a_i\neq b_j
\end{cases}
$$
其中第一行是边界条件,即空序列的最长公共子序列长度为 $0$;第二行表示当 $a_i=b_j$ 时,可以将当前元素加入前面的最长公共子序列中;第三行表示当 $a_i\neq b_j$ 时,当前元素不能同时出现在两个序列的最长公共子序列中,因此需要在 $A$ 的前 $i-1$ 个元素和 $B$ 的前 $j$ 个元素中找到最长公共子序列,或者在 $A$ 的前 $i$ 个元素和 $B$ 的前 $j-1$ 个元素中找到最长公共子序列,取较大值即可。
根据上述递推式,可以使用自底向上的方式进行求解。具体来说,可以使用一个二维数组 $dp$ 存储 $L(i,j)$ 的值,$dp[i][j]$ 表示 $A$ 的前 $i$ 个元素和 $B$ 的前 $j$ 个元素的最长公共子序列长度。初始化 $dp$ 数组为 $0$,然后按照递推式计算 $dp$ 数组中的每一个元素,最终 $dp[m][n]$ 就是 $A$ 和 $B$ 的最长公共子序列长度。
同时,可以根据 $dp$ 数组还原出最长公共子序列。具体来说,可以从 $dp[m][n]$ 开始,向左上方遍历 $dp$ 数组,每次遇到 $dp[i][j]=dp[i-1][j-1]+1$ 时,将 $a_i$ 加入最长公共子序列中,直到 $i=0$ 或 $j=0$。
下面给出一个示例:
假设 $A=1,3,2,4,5,7,6$,$B=2,4,3,6,5,8,7$,求它们的最长公共子序列。
首先,初始化 $dp$ 数组为:
$$
\begin{matrix}
& & & & & & & \\
& 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
& 0 & & & & & & \\
& 0 & & & & & & \\
& 0 & & & & & & \\
& 0 & & & & & & \\
& 0 & & & & & & \\
& 0 & & & & & & \\
\end{matrix}
$$
然后按照递推式计算 $dp$ 数组中的每一个元素,得到:
$$
\begin{matrix}
& & & & & & & \\
& 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
& 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
& 0 & 1 & 1 & 1 & 2 & 2 & 2 \\
& 0 & 1 & 1 & 2 & 2 & 2 & 2 \\
& 0 & 1 & 2 & 2 & 3 & 3 & 3 \\
& 0 & 1 & 2 & 2 & 3 & 3 & 4 \\
& 0 & 1 & 2 & 2 & 3 & 4 & 4 \\
\end{matrix}
$$
可以发现,$dp[7][6]=4$,即 $A$ 和 $B$ 的最长公共子序列长度为 $4$。
最后,根据 $dp$ 数组还原出最长公共子序列。从 $dp[7][6]$ 开始,向左上方遍历 $dp$ 数组,每次遇到 $dp[i][j]=dp[i-1][j-1]+1$ 时,将 $a_i$ 加入最长公共子序列中,直到 $i=0$ 或 $j=0$。具体来说,可以得到最长公共子序列为 $3,4,5,7$。
因此,$A$ 和 $B$ 的最长公共子序列长度为 $4$,最长公共子序列为 $3,4,5,7$。