写一下LCS问题优化的C语言代码

以下是使用动态规划空间优化的 C 代码：

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

#define MAX_N 1000

int dp[2][MAX_N+1];

int lcs(char* s1, char* s2, int len1, int len2) {
    int i, j;
    for (i = 0; i <= len1; i++) {
        for (j = 0; j <= len2; j++) {
            if (i == 0 || j == 0) {
                dp[i%2][j] = 0;
            } else if (s1[i-1] == s2[j-1]) {
                dp[i%2][j] = dp[(i-1)%2][j-1] + 1;
            } else {
                dp[i%2][j] = (dp[(i-1)%2][j] > dp[i%2][j-1]) ? dp[(i-1)%2][j] : dp[i%2][j-1];
            }
        }
    }
    return dp[len1%2][len2];
}

int main() {
    char s1[MAX_N], s2[MAX_N];
    scanf("%s%s", s1, s2);
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    printf("%d\n", lcs(s1, s2, len1, len2));
    return 0;
}

以上代码将原来的二维数组 `dp` 改为了两个一维数组，使用滚动数组的方式实现状态转移。这样可以将空间复杂度从 O(n²) 优化为 O(n)。

以下是使用树状数组优化的 C 代码：

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

#define MAX_N 1000

int c[MAX_N+1];
int dp[MAX_N+1];

int lowbit(int x) {
    return x & (-x);
}

void update(int x, int v, int n) {
    while (x <= n) {
        if (dp[x] < v) {
            dp[x] = v;
        }
        x += lowbit(x);
    }
}

int query(int x) {
    int res = 0;
    while (x > 0) {
        if (dp[x] > res) {
            res = dp[x];
        }
        x -= lowbit(x);
    }
    return res;
}

int lcs(char* s1, char* s2, int len1, int len2) {
    int i, j;
    for (i = 1; i <= len1; i++) {
        memset(c, 0, sizeof(c));
        for (j = 1; j <= len2; j++) {
            if (s1[i-1] == s2[j-1]) {
                int v = query(j-1) + 1;
                update(j, v, len2);
            }
        }
    }
    return query(len2);
}

int main() {
    char s1[MAX_N], s2[MAX_N];
    scanf("%s%s", s1, s2);
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    printf("%d\n", lcs(s1, s2, len1, len2));
    return 0;
}

以上代码使用了树状数组来维护前缀最长公共子序列的长度。时间复杂度为 O(nlogn)。