漫画：最长公共子序列

vlambda
2021-08-03

漫画：最长公共子序列

关注“脚本之家”，与百万开发者在一起

漫画：最长公共子序列

作者 l 码海

来源 l 码海

漫画：最长公共子序列

题目：

给定两个字符串 str1 和 str2，返回这两个字符串的最长公共子序列的长度

解释：一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串，如下图示：

漫画：最长公共子序列

也就是说对于以下两个字符串 str1 和 str2，其最长公共子串为「acg」。

漫画：最长公共子序列

阿宝的想法

dp 是个二维数组，即 dp[i][j], 表示对于子串 str1[0..i] 与子串 str2[0..j], 它们的最长公共子序列长度为 dp[i][j]，这样的话根据定义， dp[str1.length-1][str2.length-1] 即为所求的解。

漫画：最长公共子序列

阿宝画的状态转移表:

漫画：最长公共子序列

当两个字符串 i，j 索引对应的字符相等时，如下图示

显然dp[i][j] = dp[i-1][j-1] +1, 1 代表 i 和 j 指向的字符相等，dp[i-1][j-1] 代表除此相同字符外的 i，j 索引之前字符串的公共子序列。

2. 当两个字符串 i，j 索引对应的字符不相等时

此时 dp[i][j] 值可能为 dp[i-1][j] 或 dp[i][j-1]， dp[i-1][j] 怎么理解，既然 i 与 j 指向的字符不等，那只要丢弃 i 字符，求 str1[0..i-1] 与 str2[0..j] 的最长公共子序列即可，即 dp[i-1][j], 同理对于dp[i][j-1]，即为丢弃 j ，求 str1[0..i] 与 str2[0..j-1] 的最长公共子序列

既然 dp[i][j] 有可能等于这两个值，那么显然应该取这两者的较大值，

即dp[i][j] = max(dp[i-1][j], dp[i][j-1])。综上可知状态状态方程如下：

漫画：最长公共子序列

阿宝的想法:

空字符串与任何字符串的最长公共子序列都为 0，所以 dp[0][i], dp[j][0] 都为 0（i

为 0 到 str1 的长度， j 为 0 到 str2 的长度）,如下图蓝色部分即为 base case。

漫画：最长公共子序列

代码如下

public class Solution {
    public static int getLCS(char[] x, char[] y) {
        // base case，以下 dp 中的每个元素默认值都为 0。
        int dp[][] = new int[x.length][y.length];
        for (int i = 1; i < x.length; i++) {
            for (int j = 1; j < y.length; j++) {
                // 以下逻辑为状态转移方程
                if (x[i] == y[j]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[x.length-1][y.length-1];
    }

    public static void main(String[] args) {
        char[] x =  {' ', 'a', 'b', 'c', 'e', 'f', 'g'};
        char[] y =  {' ', 'a', 'c', 'd', 'g'};
        int lcs = getLCS(x, y);
        System.out.printf("lcs = " + lcs);
    }
}

漫画：最长公共子序列

总结

对于动态规划题型，其实套路大体相似，无非就是求出 dp 方程，再自下而上的求解，对于字符串类的动态规划题型，定义好可以先画出状态转移表，然后再据此找出状态转移方程，状态转移方程的推导有一定的技巧，根据状态（比如文中 i 和 j 对应字符是否相等）可能会有不同的情况，可以多考虑下对应的字符选或不选对应的 dp 是啥，据此推导 dp 会容易一些