二维DP问题

  • 需要维护一个二维DP表，行和列分别表示两个字符串的各个字符位置，表中的值表示两个字符串在当前位置的最长公共子序列的长度。
  • 两个字符串的当前状态为s1的第i个字符和s2和第j个字符前的子串的最长公共子序列，这个最长公共子序列由这两个字符串的前一位字符前的子串，即s1的第i-1个字符和s2的第j-1个字符前的子串的最长公共子序列决定。

如何获取公共子序列？

要获取两个字符串的最长公共子序列，首先就要知道最长公共子序列有多长，这就需要通过DP表转换为获取最长公共子序列长度问题，因为当前位置的最长公共子序列可以由前一位置的最长公共子序列决定，因此可以通过DP表由顶向下反推出最长公共子序列。

子序列和子串的区别

子序列不是子串，子串要求所有字符必须连续，子序列不要求连续，只要求相对位置不变。

最小子问题

当s1和s2两个字符串任意一个字符串长度为0时，即为空字符串时，两者都不可能有共同子序列，体现在二维DP表中为i或j为0时DP[i][j]=0，因此初始状态可以视为当s1或者s2长度为0时的状态，此时公共子序列长度都为0。

如何思考转移方程？

  • 由顶向下思考，s1和s2两个字符串达到最后一位时，如果他们的字符相同，说明这个字符是公共子序列的一部分，因此当前位置的最长公共子序列长度为（1+这两个字符串前一位置的最长公共子序列长度）。
  • 如果s1和s2这两个字符串的最后一位不相同，当前位置的字符不是公共子序列的一部分，那当前位置的最长公共子序列长度应该是前一位置的最长公共子序列长度，此时的最长公共子序列长度应该存在于以下情况：
  • s1前一位置的子串和s2当前位置子串的最长公共子序列长度
  • s2前一位置的子串和s1当前位置子串的最长公共子序列长度

上面两种情况取最大值即为当前位置的最长公共子序列长度（s1和s2不能同时取前一位置，因为这样就没有考虑当前位置的状态了）。

如何反推最长公共子序列？

  • 由顶向下分析，当s1和s2两个字符串的最后一位相同时，说明当前位置是最长公共子序列的一部分，取当前位置字符到共同子序列，并且两个字符串同时向前退一位置，考虑前一位置的最长公共子序列。
  • 如果s1和s2这两个字符串的最后一位不相同，说明当前位置的字符不是公共子序列的一部分，那么最长公共子序列可能来自于以下情况：
  • s1前一位置的子串和s2当前位置子串的最长公共子序列长度
  • s2前一位置的子串和s1当前位置子串的最长公共子序列长度

通过DP表分析两种情况的最大值，然后对应的字符串往最大值的方向移动位置即可，再进入下一次循环找更新位置后的两个子串的最长公共子序列，直到其中一个字符串移动位置后的子串只剩一个字符，因为此时再移动就会变成空串，两个字符串之间就不会再有公共子序列了。

/*
 * @Author: LibraStalker **********
 * @Date: 2023-03-26 13:30:31
 * @FilePath: BM65-最长公共子序列(二).js
 * @Description: 
 */

/**
 * longest common subsequence
 * @param s1 string字符串 the string
 * @param s2 string字符串 the string
 * @return string字符串
 */
function LCS( s1 ,  s2 ) {
    // write code here
    const s1Length = s1.length + 1;
    const s2Length = s2.length + 1;
    const dp = Array.from(new Array(s1Length), () => new Array(s2Length).fill(0));
    const resCharArr = [];

    for (let i = 1; i <= s1.length; ++i) {
        for (let j = 1; j <= s2.length; ++j) {
            if (s1[i-1] === s2[j-1]) {
                dp[i][j] = 1 + dp[i-1][j-1];
            }
            else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    // 遍历以DP数组为基准，上下标不能超过DP数组，跟上面一致，即上下标范围为1到字符串长度，当一个字符串遍历完后结束循环，因为此时已经没有公共子序列了
    for (let i = s1.length, j = s2.length; i > 0 && j > 0;) {
        if (s1[i-1] === s2[j-1]) {
            resCharArr.push(s1[i-1]);
            --i;
            --j;
        }
        else {
            if (dp[i-1][j] > dp[i][j-1]) {
                --i;  // 上面的公共子序列长度较大，s1字符串往前移动一位
            }
            else {
                --j;  // 其他情况s2字符串往前移动一位
            }
        }
    }
    
    return resCharArr.length === 0 ? "-1" : resCharArr.reverse().join("");
}
module.exports = {
    LCS : LCS
};