动态规划-----最长公共子序列(及其衍生问题)

这篇具有很好参考价值的文章主要介绍了动态规划-----最长公共子序列(及其衍生问题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一.最长公共子序列的基本概念:

解决动态规划问题的一般思路(三大步骤):

二.最长公共子序列题目:

三.字符串的删除操作:

四.最小 ASCII 删除和:


一.最长公共子序列的基本概念:

首先需要科普一下,最长公共子序列(longest common sequence)和最长公共子串(longest common substring)不是一回事儿。什么是子序列呢?即一个给定的序列的子序列,就是将给定序列中零个或多个元素去掉之后得到的结果。什么是子串呢?给定串中任意个连续的字符组成的子序列称为该串的子串。给一个图再解释一下:

动态规划-----最长公共子序列(及其衍生问题),java数据结构与算法,动态规划,算法

最长公共子序列,顾名思义,就是求两个字符串中子序列的最长的公共部分,返回这个最大的长度,比如说输入 s1 = "zabcde", s2 = "acez",它俩的最长公共子序列是 lcs = "ace",长度为 3,所以算法返回 3。

🐻🐻🐻对于两个字符串求子序列的问题,都是用两个指针 i 和 j 分别在两个字符串上移动,大概率是动态规划思路

解决动态规划问题的一般思路(三大步骤):

动态规划,无非就是利用历史记录,来避免我们的重复计算。而这些历史记录,我们得需要一些变量来保存,一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤:

  • 🧐 步骤一:定义dp数组元素的含义
  • 🧐步骤二:找出数组元素之间的关系式(也就是我们所熟知的状态转移方程)
  • 🧐第三步骤:找出初始值(base case)

接下来的题目我们会按照这三个步骤来解释说明

二.最长公共子序列题目:

计算最长公共子序列(Longest Common Subsequence,简称 LCS)是一道经典的动态规划题目,力扣第 1143 题「最长公共子序列open in new window」就是这个问题:

对应的函数签名如下:

动态规划-----最长公共子序列(及其衍生问题),java数据结构与算法,动态规划,算法

  • 步骤一:按我上面的步骤说的,首先我们来定义 dp数组的含义,题目要我们求两个字符串的最长公共子序列,给出 对应dp[][] 数组的定义:dp[i][j] 表示串 s1[0..i] 和 s2[0..j] 最长公共子序列的长度
  • 步骤二:找到数组元素之间的关系式(也就是我们所熟知的状态转移方程)

这里咱不要看 s1 和 s2 两个字符串,而是要具体到每一个字符,思考每个字符该做什么:

①.如果我们只看 s1[i] 和 s2[j]如果 s1[i] == s2[j],说明这个字符一定在 lcs 中: 

动态规划-----最长公共子序列(及其衍生问题),java数据结构与算法,动态规划,算法

根据dp数组定义可得此时状态转移方程为:dp[ i ][ j ] = 1 + dp[ i - 1 ][ j - 1 ]

②.如果s[i] != s2[j] 意味着,s1[i] 和 s2[j] 中至少有一个字符不在 lcs 中

动态规划-----最长公共子序列(及其衍生问题),java数据结构与算法,动态规划,算法

因为是求最长的公共子序列,所以我们求出对应上述的三种情况的最大值即可,由于情况三被一和二所包(因为我们在求最大值嘛,情况三在计算 s1[i+1..] 和 s2[j+1..] 的 lcs 长度,这个长度肯定是小于等于情况二 s1[i..] 和 s2[j+1..] 中的 lcs 长度的,因为 s1[i+1..] 比 s1[i..] 短嘛,那从这里面算出的 lcs 当然也不可能更长嘛)所以可得:

根据dp数组定义可得此时状态转移方程为:dp[ i ][ j ] = Math.max( dp [ i - 1][ j ],dp[ i ] [ j - 1 ])

  •  步骤三:找出初始值(base case):这里当字符串为空时,没有最大公共子序列,对应的值为0。

我们以ABCB  和 BDCA 为例-----》填dp表:

动态规划-----最长公共子序列(及其衍生问题),java数据结构与算法,动态规划,算法

按照上述的状态转移方程,我们可以将表填完整:

动态规划-----最长公共子序列(及其衍生问题),java数据结构与算法,动态规划,算法

最后,完成上述过程后,动态规划完整代码:

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(),n = text2.length();
       // base case: dp[0][..] = dp[..][0] = 0
        int dp[][] = new int[m + 1][n + 1];
        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= n;j++){
                if(text1.charAt(i - 1) == text2.charAt(j - 1)){
                 // text1[i-1] 和 text2[j-1] 必然在 lcs 中
                    dp[i][j] = 1 + dp[i - 1][j -1];
                }else{
                  // text1[i-1] 和 text2[j-1] 至少有一个不在 lcs 中
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

这里还有一种带备忘录的递归式解法,与上面的方法类似:

class Solution {
    // 备忘录,消除重叠子问题
    int[][] memo;

    /* 主函数 */
    public int longestCommonSubsequence(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        // 备忘录值为 -1 代表未曾计算
        memo = new int[m][n];
        for (int[] row : memo) 
            Arrays.fill(row, -1);
        // 计算 s1[0..] 和 s2[0..] 的 lcs 长度
        return dp(s1, 0, s2, 0);
    }

    // 定义:计算 s1[i..] 和 s2[j..] 的最长公共子序列长度
    int dp(String s1, int i, String s2, int j) {
        // base case
        if (i == s1.length() || j == s2.length()) {
            return 0;
        }
        // 如果之前计算过,则直接返回备忘录中的答案
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        // 根据 s1[i] 和 s2[j] 的情况做选择
        if (s1.charAt(i) == s2.charAt(j)) {
            // s1[i] 和 s2[j] 必然在 lcs 中
            memo[i][j] = 1 + dp(s1, i + 1, s2, j + 1);
        } else {
            // s1[i] 和 s2[j] 至少有一个不在 lcs 中
            memo[i][j] = Math.max(
                dp(s1, i + 1, s2, j),
                dp(s1, i, s2, j + 1)
            );
        }
        return memo[i][j];
    }
}

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

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

动态规划-----最长公共子序列(及其衍生问题),java数据结构与算法,动态规划,算法

如果 s1[i] = s2[j],那么当前字符肯定在最长公共子序列中;否在我们就向左或者向上遍历,至于选择「向左」还是「向上」的方向,这就要和构造 dp 的时候联系起来。我们是挑了一个最大值,所以遍历的方向也是谁大就往谁的方向遍历 ,具体代码:

public static int lcs(String s1,String s2){
       //最长公共子序列框架
        int m = s1.length(),n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1;i <= m;i++){
            for(int j = 1;j <=n;j++){
                if(s1.charAt(i - 1) == s2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = Math.max(
                            dp[i - 1][j],
                            dp[i][j - 1]
                    );
                }
            }
        }
        //打印最长公共子序列
        int i  = m,j = n;
        StringBuffer sb = new StringBuffer();
        while(i > 0 && j > 0){
            char c1 = s1.charAt(i - 1);
            char c2 = s2.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());
        return dp[m][n];
    }

有了上面的对最长公共子序列的一定了解,下面,来看两道和最长公共子序列相似的两道题目

三.字符串的删除操作:

这是力扣第 583 题「两个字符串的删除操作open in new window」,看下题目:

给定两个单词 s1 和 s2 ,返回使得 s1 和 s2 相同所需的最小步数。每步可以删除任意一个字符串中的一个字符。比如输入 s1 = "sea" s2 = "eat",算法返回 2,第一步将 "sea" 变为 "ea" ,第二步将 "eat" 变为 "ea"

函数签名如下:

动态规划-----最长公共子序列(及其衍生问题),java数据结构与算法,动态规划,算法

题目让我们计算将两个字符串变得相同的最少删除次数,那我们可以思考一下,最后这两个字符串会被删成什么样子?删除的结果不就是它俩的最长公共子序列嘛!那么,要计算删除的次数,就可以通过最长公共子序列的长度推导出来:word1.len - LCS + word2.len - LCS 

与上面的解答类似:

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(),n = word2.length();
        int longest = lcs(word1,word2);
      //推导出的公式
        return m - longest + n - longest;
    }
    int lcs(String s1,String s2){
       //基本最长公共子序列的框架不变
        int m = s1.length(),n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= n;j++){
                if(s1.charAt(i - 1) == s2.charAt(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]
                    );
                }
            }
        }
        return dp[m][n];
    }
}

四.最小 ASCII 删除和:

这是力扣第 712 题「两个字符串的最小 ASCII 删除和open in new window」,题目和上一道题目类似,只不过上道题要求删除次数最小化,这道题要求删掉的字符 ASCII 码之和最小化。

动态规划-----最长公共子序列(及其衍生问题),java数据结构与算法,动态规划,算法

对应函数签名:

动态规划-----最长公共子序列(及其衍生问题),java数据结构与算法,动态规划,算法

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

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

  • 步骤一:结合这个题目我们把 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):动态规划-----最长公共子序列(及其衍生问题),java数据结构与算法,动态规划,算法

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

 至此,我们完成了其推导过程,动态规划解法代码:

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length(),n = s2.length();
      //创建dp表
        int[][] dp = new int[m + 1][n + 1];
      //初始化dp表
        dp[0][0] = 0;
        for(int i = 1;i <= m;i++){
            dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
        }
        for(int j = 1;j <= n;j++){
            dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1);
        }
        //填表
        for(int i = 1;i <= m;i++){
           for(int j = 1;j <= n;j++){
            //相等情况
            if(s1.charAt(i - 1) == s2.charAt(j - 1)){
                dp[i][j] = dp[i - 1][j - 1];
            }else{
                //不相等情况
                dp[i][j] = Math.min(
                   s1.charAt(i - 1) + dp[i - 1][j],
                   s2.charAt(j - 1) + dp[i][j - 1]
                );
            }
           }
        }
      //返回值
        return dp[m][n];
    }
}

参考文章:《labuladong的算法笔记》,告别动态规划,连刷40道动规算法题,我总结了动规的套路-CSDN博客

结语: 写博客不仅仅是为了分享学习经历,同时这也有利于我巩固自己的知识点,总结该知识点,由于作者水平有限,对文章有任何问题的还请指出,接受大家的批评,让我改进。同时也希望读者们不吝啬你们的点赞+收藏+关注,你们的鼓励是我创作的最大动力!

动态规划-----最长公共子序列(及其衍生问题),java数据结构与算法,动态规划,算法文章来源地址https://www.toymoban.com/news/detail-843482.html

到了这里,关于动态规划-----最长公共子序列(及其衍生问题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode1143. 最长公共子序列-动态规划(java)

    leetcode1143. 最长公共子序列 来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/longest-common-subsequence 给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。 一个字符串的 子序列 是指这样一个新的字符串: 它是由原字

    2024年01月19日
    浏览(9)
  • 动态规划--最长公共子序列

    动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题﹐ 即将大规模变成小规模 ,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是﹐适合于用动态规划法求解的问题,经分解得到的子问题往往不是互相独立的。 他们之间有关系

    2024年02月04日
    浏览(13)
  • 动态规划——最长公共子序列

    先来讲解以下什么是最长公共子序列。最长公共子序列不是最长相同字符串,有点相似但不一样,来举个简单的例子,有字符串s1=bcdea,s2=abce,最长相同字符串是bc,最大公共部分是2;而最长公共子序列则是bce,最大公共部分是3。可以看出,公共子序列不需要连续相等,有相

    2023年04月19日
    浏览(10)
  • 算法:动态规划——最长公共子序列

    动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 与分治法不同的是,适合于用动态规划法求解的问题,经分解得到的子问题往往不是互相独立的。若用分治法解这类问题,则分解得到的

    2023年04月27日
    浏览(14)
  • 【算法-动态规划】最长公共子序列

    2024年01月23日
    浏览(11)
  • 动态规划之最长公共子序列模板

    夏令营:动态规划特训 - 【算法模板题】最长公共子序列 - 蓝桥云课 (lanqiao.cn) 我们来解释一下状态转移方程吧。 dp[i][j]的含义是第i个和第j个字符,i与j的下标从1开始,代表着原子符串的第一个字符。那么理所当然字符串a的第0个字符和字符串b的0个字符的公共长度为0.如果字

    2024年02月12日
    浏览(7)
  • 【动态规划】最长公共子序列Python实现

    个人主页:丷从心 系列专栏:动态规划算法 问题描述 给定两个序列 X = {   x 1 , x 2 , ⋯   , x m   } X = set{x_{1} , x_{2} , cdots , x_{m}} X = { x 1 ​ , x 2 ​ , ⋯ , x m ​ } 和 Y = {   y 1 , y 2 , ⋯   , y n   } Y = set{y_{1} , y_{2} , cdots , y_{n}} Y = { y 1 ​ , y 2 ​ , ⋯ , y n ​ } ,找出 X X X

    2024年02月20日
    浏览(9)
  • 动态规划-最长公共子序列(c语言)

    实验 3: 最长公共子序列 内容: 给定两个字符串str1和str2,输出两个字符串的最长公共子序列,如果最长公共子序列为空,则返回“-1”。目前给出的数据,仅仅会存在一个最长的公共子序列。 数据范围: 0 ≤|str1|,|str2|≤2000 要求: 空间复杂度O(n 2 ) 具体思路: step1:

    2024年02月04日
    浏览(11)
  • 两个数组的动态规划——最长公共子序列模型

    1.考虑空串,即dp表多出一行一列, 代表某个字符串为空。 2.考虑最后一个位置;是否相等; 3.可在字符串最前面加虚拟位置以对应映射关系; 4.一般横行是j,列是i。此时第一行代表第二个字符串不为空,即第一个字符串是空的 给你两个字符串  s   和  t  ,统计并返回在

    2024年03月10日
    浏览(19)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包