最长公共子序列动态规划算法c语言
时间: 2023-08-07 20:17:46 浏览: 53
最长公共子序列是指在两个序列中,找到一个最长的子序列,使得它在两个序列中的相对位置都相同。下面是使用动态规划算法求解最长公共子序列的C语言代码:
```c
#include <stdio.h>
#include <string.h>
#define MAXLEN 100 //最大序列长度
int dp[MAXLEN][MAXLEN]; //记录最长公共子序列的长度
int LCS(char *str1, char *str2, int len1, int len2)
{
int i, j;
//初始化第一行和第一列
for (i = 0; i <= len1; i++)
dp[i][0] = 0;
for (j = 0; j <= len2; j++)
dp[0][j] = 0;
//动态规划求解
for (i = 1; i <= len1; i++)
{
for (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][j-1] > dp[i-1][j]) ? dp[i][j-1] : dp[i-1][j];
}
}
//返回最长公共子序列的长度
return dp[len1][len2];
}
int main()
{
char str1[MAXLEN], str2[MAXLEN];
int len1, len2, lcs_len;
//读入两个字符串
printf("请输入第一个字符串:");
gets(str1);
printf("请输入第二个字符串:");
gets(str2);
//计算最长公共子序列的长度
len1 = strlen(str1);
len2 = strlen(str2);
lcs_len = LCS(str1, str2, len1, len2);
//输出结果
printf("最长公共子序列的长度为:%d\n", lcs_len);
return 0;
}
```
其中,dp[i][j]表示str1的前i个字符和str2的前j个字符的最长公共子序列的长度。在动态规划求解时,如果str1[i-1]等于str2[j-1],则当前字符可以加入最长公共子序列中,此时dp[i][j]等于dp[i-1][j-1]+1;否则,当前字符不能加入最长公共子序列中,此时dp[i][j]等于dp[i][j-1]和dp[i-1][j]中的较大值。最终,dp[len1][len2]即为最长公共子序列的长度。