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

本文主要是介绍动态规划-----最长公共子序列（及其衍生问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

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

三.字符串的删除操作：

四.最小 ASCII 删除和：

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

首先需要科普一下，最长公共子序列（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] = 0int 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 caseif (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];}
}