最长公共子序列 (LCS)：「模版」&「输出」

「最长递增子序列」针对一个字符串，求出其最长递增子序列 (废话文学！！) 详细介绍可见动态规划设计：最长递增子序列

「最长重复子数组」针对两个数组，求出其最长重复子数组 (子数组必须要连着) 详细介绍可见最长重复子数组

而我们今天要介绍的是「最长公共子序列」，它是针对两个字符串，求出其最长公共子序列 (子序列可以不用连着)

模版归纳

首先结合题目 最长公共子序列，归纳总结出「最长公共子序列」问题的模版

毫无疑问这种类型的题目需要使用「DP」去解决！！这里给出一个例子s1 = "abcde", s2 = "ace"，下面所有分析都围绕该样例展开

先给出dp[][]数组的定义：dp[i][j]表示子串s1[0..i]和s2[0..j]最长公共子序列的长度

那么「状态转移方程」是什么呢？

如果s1[i] = s2[j]，dp[i][j] = dp[i - 1][j - 1] + 1
如果s1[i] != s2[j]，dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j])

为什么就是这样转移的呢？直接看下图：

那么「base case」是什么呢？

如上图粉色标记出来的就是 base case。橙色标记出来的是相等的情况，其余是不等的情况

完整模版


public int longestCommonSubsequence(String text1, String text2) {
    int n1 = text1.length(), n2 = text2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            char c1 = text1.charAt(i - 1);
            char c2 = text2.charAt(j - 1);
            // 相等情况
            if (c1 == c2) dp[i][j] = dp[i - 1][j - 1] + 1;
            // 不等情况
            else dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
        }
    }
    return dp[n1][n2];
}

如何输出最长公共子序列

「最长公共子序列」问题基本都是要求返回一个最值即可，但是有时候面试官喜欢不按常理出牌，让你输出最长公共子序列

我们可以通过构造出来的二维dp数组来得到最长公共子序列。如下图所示，从最后一个点开始往左上角的方向遍历

如果s1[i] = s2[j]，那么当前字符肯定在最长公共子序列中；否在我们就向左或者向上遍历

至于选择「向左」还是「向上」的方向，这就要和构造dp的时候联系起来。我们是挑了一个最大值，所以遍历的方向也是谁大就往谁的方向遍历


xxxxxxxxxx
public int longestCommonSubsequence(String text1, String text2) {
    
    // 同上面的模版
    
    /* ------- print ------- */
    int i = n1, j = n2;
    StringBuffer sb = new StringBuffer();
    while (i > 0 && j > 0) {
        char c1 = text1.charAt(i - 1);
        char c2 = text2.charAt(j - 1);
        if (c1 == c2) {
            sb.append(c1);
            // 向左上角遍历
            i--; j--;
        } else {
            // 向上
            if (dp[i - 1][j] > dp[i][j - 1]) i--;
            // 向左
            else j--;
        }
    }
    System.out.println(sb.reverse());
    /* ------- end ------- */
    return dp[n1][n2];
}

两个字符串的最小ASCII删除和

题目详情可见两个字符串的最小ASCII删除和

其实这个题目的底层也是「最长公共子序列」，只是问法稍微变化了一点

「需要被删除的字符 = 原字符串 - 最长公共子序列」

结合这个题目我们把dp[][]数组的定义稍微改改：dp[i][j]表示子串s1[0..i]和s2[0..j]最小 ASCII 删除和

那么「状态转移方程」是什么呢？(有点逆过程的意思！！！)

如果s1[i] = s2[j]，dp[i][j] = dp[i - 1][j - 1] (不需要被删除)
如果s1[i] != s2[j]，dp[i][j] = Math.min(dp[i - 1][j] + s1[i], dp[i][j - 1] + s2[j])

那么「base case」是什么呢？

如上图粉色标记出来的就是 base case，e表示 e 的 ASCII 值


xxxxxxxxxx
public int minimumDeleteSum(String s1, String s2) {
    int n1 = s1.length(), n2 = s2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];
    // base case
    for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
    for (int i = 1; i <= n2; i++) dp[0][i] = dp[0][i - 1] + s2.charAt(i - 1);
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            int c1 = s1.charAt(i - 1);
            int c2 = s2.charAt(j - 1);
            // 相等情况
            if (c1 == c2) dp[i][j] = dp[i - 1][j - 1];
            // 不等情况
            else dp[i][j] = Math.min(dp[i][j - 1] + c2, dp[i - 1][j] + c1);
        }
    }
    return dp[n1][n2];
}