动态规划法最长公共子序列c++

动态规划法求解最长公共子序列（LCS）问题，是一种常见的字符串匹配问题，可以用于计算两个字符串的相似程度或者找出两个字符串的最长公共子串。以下是求解最长公共子序列的C语言实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX(a, b) ((a) > (b) ? (a) : (b))

int lcs(char *str1, char *str2, int len1, int len2)
{
    int i, j;
    int **dp = (int **)malloc(sizeof(int *) * (len1 + 1));
    for (i = 0; i <= len1; i++) {
        dp[i] = (int *)malloc(sizeof(int) * (len2 + 1));
        memset(dp[i], 0, sizeof(int) * (len2 + 1));
    }

    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] = MAX(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    int res = dp[len1][len2];

    for (i = 0; i <= len1; i++) {
        free(dp[i]);
    }
    free(dp);

    return res;
}

int main()
{
    char *str1 = "ABCDGH";
    char *str2 = "AEDFHR";

    int len1 = strlen(str1);
    int len2 = strlen(str2);

    printf("Length of LCS is %d\n", lcs(str1, str2, len1, len2));

    return 0;
}

在这个实现中，我们使用一个二维数组 `dp` 来记录两个字符串的所有子序列的长度。其中 `dp[i][j]` 表示字符串 `str1` 的前 `i` 个字符与字符串 `str2` 的前 `j` 个字符的最长公共子序列长度。接下来，我们依次遍历两个字符串的字符，如果当前字符相同，则将 `dp[i][j]` 设置为 `dp[i-1][j-1] + 1`。否则，取 `dp[i-1][j]` 和 `dp[i][j-1]` 中的最大值作为 `dp[i][j]` 的值。最后，返回 `dp[len1][len2]` 即为最长公共子序列的长度。

需要注意的是，在实现中我们使用了动态内存分配来创建二维数组 `dp` ，在使用完毕后需要释放内存。