给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},用动态规划算法找出X和Y的最长公共子序列,用C实现该算法。并给出该算法思想描述
时间: 2024-05-05 13:22:51 浏览: 18
算法思想描述:
1. 定义状态:dp[i][j]表示X的前i个字符和Y的前j个字符的最长公共子序列的长度。
2. 初始化:dp[0][j]=dp[i][0]=0,表示空序列与任何序列的最长公共子序列长度都为0。
3. 状态转移方程:当X[i]=Y[j]时,dp[i][j]=dp[i-1][j-1]+1,即当前字符相同时,最长公共子序列的长度加一,否则,dp[i][j]=max(dp[i-1][j],dp[i][j-1])。
4. 最终答案:dp[m][n]即为最长公共子序列的长度。
C代码实现:
```c
#include <stdio.h>
#include <string.h>
#define MAXN 1000
int max(int a, int b) {
return a > b ? a : b;
}
int LCS_length(char *X, char *Y, int m, int n) {
int dp[MAXN][MAXN];
memset(dp, 0, sizeof(dp)); // 初始化为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-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
}
int main() {
char X[MAXN], Y[MAXN];
scanf("%s%s", X, Y);
int m = strlen(X), n = strlen(Y);
int ans = LCS_length(X, Y, m, n);
printf("%d\n", ans);
return 0;
}
```
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![text/x-c](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)
![](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)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)