目录
一.最长公共子序列的基本概念：
解决动态规划问题的一般思路（三大步骤）：
二.最长公共子序列题目：
三.字符串的删除操作：
四.最小 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] = 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博客
结语： 写博客不仅仅是为了分享学习经历，同时这也有利于我巩固自己的知识点，总结该知识点，由于作者水平有限，对文章有任何问题的还请指出，接受大家的批评，让我改进。同时也希望读者们不吝啬你们的点赞+收藏+关注，你们的鼓励是我创作的最大动力！
推荐文章
您阅读本篇文章共花了：
发表评论