请使用c语言实现最长公共子序列的动态规划算法
时间: 2024-04-29 08:22:31 浏览: 8
好的,我可以为您演示使用C语言实现最长公共子序列的动态规划算法。以下是代码:
```
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 100
int main() {
// 输入两个字符串
char str1[MAX_SIZE], str2[MAX_SIZE];
printf("请输入第一个字符串: ");
scanf("%s", str1);
printf("请输入第二个字符串: ");
scanf("%s", str2);
// 初始化动归数组
int len1 = strlen(str1);
int len2 = strlen(str2);
int dp[len1 + 1][len2 + 1];
for (int i = 0; i <= len1; i++) {
for (int j = 0; j <= len2; j++) {
dp[i][j] = 0;
}
}
// 动态规划求解最长公共子序列
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (str1[i - 1] == str2[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[len1][len2]);
return 0;
}
```
这个程序使用动态规划算法,分别计算两个字符串中每个可能的子序列的长度,最终得到两个字符串的最长公共子序列的长度。