C语言动态规划求两个数组最长公共连续子序列

以下是C语言实现动态规划求两个数组最长公共连续子序列的代码：

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

int lcs(int* arr1, int* arr2, int m, int n)
{
    int** dp = (int**)malloc((m+1)*sizeof(int*));
    for (int i = 0; i <= m; i++) {
        dp[i] = (int*)malloc((n+1)*sizeof(int));
    }

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (arr1[i-1] == arr2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = 0;
            }
        }
    }

    int max_len = 0;
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (dp[i][j] > max_len) {
                max_len = dp[i][j];
            }
        }
    }

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

    return max_len;
}

int main()
{
    int arr1[] = {1, 2, 3, 4, 5, 6};
    int arr2[] = {3, 4, 5, 6, 7, 8, 9};
    int m = sizeof(arr1) / sizeof(int);
    int n = sizeof(arr2) / sizeof(int);

    int len = lcs(arr1, arr2, m, n);
    printf("The length of longest common subsequence is %d\n", len);

    return 0;
}

上述代码中，我们使用一个二维数组dp来记录两个数组的最长公共连续子序列。其中，dp[i][j]表示arr1中前i个元素和arr2中前j个元素的最长公共连续子序列长度。当arr1[i-1]等于arr2[j-1]时，说明两个数组的第i个元素和第j个元素相同，此时dp[i][j]等于dp[i-1][j-1]+1；否则，dp[i][j]等于0。最终，我们在dp数组中找到最大的元素即可得到两个数组的最长公共连续子序列长度。