第一题

在构建 c 数组时，不再维护额外的 b 数组来记录方向。在需要回溯寻找具体的最长公共子序列时，直接通过比较 c[i] [j]、c[i-1] [j] 和 c[i] [j-1] 的值来判断当前字符是否属于最长公共子序列，以及应该向哪个方向回溯。

伪代码

FUNCTION LCS(const string s1, const string s2):
    m = s1.size() // 获取字符串 s1 的长度
    n = s2.size() // 获取字符串 s2 的长度
    dp[m+1][n+1] // 初始化动态规划表
    for i from 1 to m:
        for j from 1 to n: 
            if s1[i-1] == s2[j-1]: // 如果当前字符相同
                dp[i][j] = dp[i-1][j-1] + 1 // 当前位置的 LCS 长度等于左上方的值加 1，表示找到了一个公共子序列字符
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])                 // 如果当前字符不同，当前位置的 LCS 长度取上方和左方的最大值，表示不考虑当前字符
        end for
    end for

    return dp[m][n] // 返回最终的最长公共子序列长度，位于动态规划表的右下角
END FUNCTION

GALA-Lin原创5/7/25大约 6 分钟