C程序中LCS的空间优化解决方案？

什么是LCS？

LCS，即Longest Common Subsequence，最长公共子序列，是指两个序列中的最长的公共部分。例如序列"ABCADAB"和"ACBAAB"的LCS为"ABA"。

传统LCS算法的空间复杂度问题

传统的LCS算法，通常使用动态规划的方法来解决问题。一般而言，其时间复杂度为O(mn)，空间复杂度也为O(mn)。其中，m和n分别为两个序列的长度。具体实现过程如下：

初始化

for(int i = 1; i <= m; ++i)

    for(int j = 1; j <= n; ++j)
        dp[i][j] = 0;

其中，dp[i][j]表示序列1的前i个字符和序列2的前j个字符的LCS长度。

状态转移

for(int i = 1; i <= m; ++i)

    for(int j = 1; j <= n; ++j){
        if(s1[i] == s2[j])
            dp[i][j] = dp[i - 1][j - 1] + 1;
        else
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    }

其中，s1和s2分别为两个序列。

LCS长度

cout << dp[m][n] << endl;

根据dp数组的状态，可以求出LCS的长度。

然而，这样的算法使用了O(mn)的空间，对于长度较长的字符串，空间开销便很大。因此，需要想办法优化空间复杂度。

空间优化解决方案

对上述经典的dp算法，我们可以尝试用滚动数组的方式来优化空间复杂度。具体而言，我们只需要把dp数组从二维降到一维。

状态转移

for(int j = 1; j <= n; ++j){

    int last = 0; // 上一个dp[i - 1][j - 1]
    for(int i = 1; i <= m; ++i){
        int tmp = dp[i]; // 临时存储dp[i][j]
        if(s1[i] == s2[j])
            dp[i] = last + 1;
        else
            dp[i] = max(dp[i], dp[i - 1]);
        last = tmp;
    }
}

可以看到，我们只需要一次遍历n，每次遍历m。因此，空间复杂度可以降为O(m)。

LCS

此时，求出LCS就需要用其他的思路了。具体而言，我们可以从dp数组的右下角进行倒推，倒推回原始的两个序列中有哪些字符是公共的。

int len = dp[m]; // LCS的长度

char lcs[100]; // 用数组存储LCS
int p = len - 1; // lcs数组的下标
int i = m, j = n;
while(i && j){ // 倒推
    if(dp[i] == dp[i - 1])
        --i;
    else if(dp[i] == dp[i] = dp[i - 1] + 1){
        lcs[p] = s1[i];
        --p;
        --i;
        --j;
    }
    else
        --j;
}
for(i = 0; i < len; ++i)
    cout << lcs[i];
cout << endl;

其中，s1和s2分别为原始的序列。

总结

对于LCS问题，我们可以通过动态规划实现，但是其空间复杂度很高。利用滚动数组的方式，我们可以将空间复杂度降为O(m)，然后通过倒推的方式，求出LCS。