C语言用自底向上方式求解最长公共子序列问题,给出最优值和最优解
时间: 2023-06-10 18:07:08 浏览: 44
最长公共子序列问题可以用动态规划求解,其中自底向上方式是一种较为常见的实现方式。
假设有两个序列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
```