vlambda博客
学习文章列表

漫画:最长公共子序列

 关注脚本之家,与百万开发者在一起

漫画:最长公共子序列

作者 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] 即为所求的解。

漫画:最长公共子序列

漫画:最长公共子序列

阿宝画的状态转移表:
漫画:最长公共子序列

漫画:最长公共子序列

漫画:最长公共子序列

漫画:最长公共子序列

  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 会容易一些


推荐阅读:


漫画:最长公共子序列

                        
                          
                          
                        

每日打卡赢积分兑换书籍入口

👇🏻👇🏻👇🏻