给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},用动态规划算法找出X和Y的最长公共子序列,用C/C++实现该算法。
时间: 2024-05-02 14:23:30 浏览: 11
动态规划算法的核心思想是将原问题分解为若干个子问题,逐个求解子问题,最后合并子问题得到原问题的解。在最长公共子序列问题中,我们可以将原问题分解为以下子问题:
1. 当 Xi==Yj 时,LCS(X[1:i],Y[1:j])=LCS(X[1:i-1],Y[1:j-1])+1
2. 当 Xi!=Yj 时,LCS(X[1:i],Y[1:j])=max(LCS(X[1:i],Y[1:j-1]),LCS(X[1:i-1],Y[1:j]))
因此,我们可以定义一个二维数组dp[m+1][n+1],其中dp[i][j]表示X[1:i]和Y[1:j]的最长公共子序列长度。
具体实现代码如下:
```c
#include <stdio.h>
#include <string.h>
#define MAX_LEN 100
int dp[MAX_LEN + 1][MAX_LEN + 1];
int max(int a, int b) {
return a > b ? a : b;
}
int lcs(char *x, char *y) {
int m = strlen(x);
int n = strlen(y);
for (int i = 0; i <= m; ++i) {
dp[i][0] = 0;
}
for (int j = 0; j <= n; ++j) {
dp[0][j] = 0;
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (x[i - 1] == y[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[m][n];
}
int main() {
char x[MAX_LEN + 1], y[MAX_LEN + 1];
printf("请输入序列 X:");
scanf("%s", x);
printf("请输入序列 Y:");
scanf("%s", y);
int len = lcs(x, y);
printf("X 和 Y 的最长公共子序列长度为:%d\n", len);
return 0;
}
```
注意,本代码中的序列下标从1开始,因此在比较时需要将下标减1。