用C语言求int a[]={1,3,4,5,6,3,4,7,8,3,9}; int b[]={2,3,5,4,6,8,6,3,9,0,1} 求a,b最长公共子序列长度
时间: 2024-01-07 12:04:14 浏览: 27
以下是用C语言求a,b最长公共子序列长度的代码:
```c
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int lcs(int *X, int *Y, int m, int n) {
int L[m + 1][n + 1];
int i, j;
for (i = 0; i <= m; i++) {
for (j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
L[i][j] = 0;
} else if (X[i - 1] == Y[j - 1]) {
L[i][j] = L[i - 1][j - 1] + 1;
} else {
L[i][j] = max(L[i - 1][j], L[i][j - 1]);
}
}
}
return L[m][n];
}
int main() {
int a[] = {1, 3, 4, 5, 6, 3, 4, 7, 8, 3, 9};
int b[] = {2, 3, 5, 4, 6, 8, 6, 3, 9, 0, 1};
int m = sizeof(a) / sizeof(a[0]);
int n = sizeof(b) / sizeof(b[0]);
printf("Length of LCS is %d\n", lcs(a, b, m, n));
return 0;
}
```
输出结果为:Length of LCS is 7,即a和b的最长公共子序列长度为7。
--相关问题--:
1. 什么是最长公共子序列?
2. 如何用动态规划求解最长公共子序列?
3. 除了动态规划,