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

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

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

最长公共子序列，顾名思义，就是求两个字符串中子序列的最长的公共部分，返回这个最大的长度，比如说输入 ***

s1 = "zabcde", s2 = "acez"

*，它俩的最长公共子序列是

lcs = "ace"

**，长度为 3，所以算法返回 3。

**🐻🐻🐻对于两个字符串求子序列的问题，都是用两个指针

i

和

j

分别在两个字符串上移动，大概率是动态规划思路**。

解决动态规划问题的一般思路（三大步骤）：

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

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

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

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

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

对应的函数签名如下：

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

这里**咱不要看

s1

和

s2

两个字符串，而是要具体到每一个字符，思考每个字符该做什么：**

①.如果我们只看**

s1[i]

和

s2[j]

，如果

s1[i] == s2[j]

，说明这个字符一定在

lcs

中**：

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

**

②.如果s[i] != s2[j]

意味着，

s1[i]

和

s2[j]

中至少有一个字符不在

lcs

中**：

因为是求最长的公共子序列，所以我们求出对应上述的三种情况的最大值即可，由于情况三被一和二所包（因为我们在求最大值嘛，情况三在计算

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表：

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

最后，完成上述过程后，动态规划完整代码：

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

数组来得到最长公共子序列。如下图所示，从最后一个点开始往左上角的方向遍历 ：

如果

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"

。

函数签名如下：

题目让我们计算将两个字符串变得相同的最少删除次数，那我们可以思考一下，最后这两个字符串会被删成什么样子？删除的结果不就是它俩的最长公共子序列嘛！那么，要计算删除的次数，就可以通过最长公共子序列的长度推导出来：**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 码之和最小化。

对应函数签名：

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

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

• **步骤一:**结合这个题目我们把 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 值

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

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博客

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