C语言用动态规划求最长公共子序列
时间: 2023-06-28 22:11:14 浏览: 66
动态规划求最长公共子序列的思路如下:
首先,我们定义一个二维数组dp[m+1][n+1],其中m和n分别为两个字符串的长度加1。
接着,我们从两个字符串的第一个字符开始比较,依次填充dp数组。具体地,假设两个字符串分别为s1和s2,当前比较到的字符索引分别为i和j,则有以下三种情况:
1. 如果s1[i] == s2[j],那么这两个字符属于最长公共子序列中的一部分,因此dp[i][j] = dp[i-1][j-1] + 1。
2. 如果s1[i] != s2[j],那么这两个字符不可能同时出现在最长公共子序列中,因此我们需要从dp[i-1][j]和dp[i][j-1]中选取一个较大的值作为dp[i][j]的值。
3. 如果i或j等于0,说明有一个字符串已经比较完了,此时dp[i][j]的值为0。
最后,dp[m][n]就是最长公共子序列的长度。
下面是C语言实现代码:
```c
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
return a > b ? a : b;
}
int lcs(char *s1, char *s2) {
int m = strlen(s1);
int n = strlen(s2);
int dp[m+1][n+1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i-1] == s2[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 s1[] = "ABCD";
char s2[] = "BD";
printf("%d\n", lcs(s1, s2)); // 输出2
return 0;
}
```