动态规划算法：字符串类问题（2）公共串

0 前言

上节课我们已经讲述了使用动态规划求取回文串长度与数量的方法（和本节课关系不大，感兴趣可以去看字符串类问题（1）回文串），这节课我们继续探索字符串问题中的动态规划问题。

进入本篇文章前，需要给大家普及两个概念：
（1）子串/子数组：从原字符串上截取的一段连续的字符串
（2）子序列：可以删除掉中间某些元素，不改变剩余元素相对位置的子集合

1、公共子串

1.1 题目描述

最长重复子数组 - 力扣
给两个整数数组 nums1 和 nums2 ，返回两个数组中公共的、长度最长的子数组的长度 。

1.2 题目分析

读题，发现这道题要求我们求公共子数组，或者说是公共子串（后面我会混着说，大家别混淆），要求连续。
说实话，这道题即使用暴力解法，代码量也不小，思路是把nums1的所有可能的子数组放入unordered_set中，再把nums2所有可能的子数组找出来在哈希表中查询。如果题目要求我们输出最长子串内的每个元素，那我们只能这么做。但是这道题只要求我们输出长度。
这道题属于双字符串动态规划的基础问题，没做过很难想出来，除非你是天才，因此我把dp数组的思考过程直接给大家。

1.2.1 dp数组的定义：

一般来说，涉及到两个字符串的递归，我们需要设计二维dp数组。
这里定义dp[i][j]为：在nums1的索引[0, i] 与nums2的索引[0, j]内寻找公共子串，公共子串的最后一个元素必须与nums1[i]与nums2[j]相等，子串的长度为dp[i][j]。
就是把nums1与nums2先分割开，只看前半部分，寻找内部可能的最大公共子串。

假设

nums1 = {0, 1, 2, 3};
nums2 = {1, 2, 3};

dp[2][1]就表示在nums1[0:2] = {0, 1, 2}与nums2[0:1] = {1, 2}中找公共子串，同时要求子串的最后一个元素必须与nums1[2] = 2与nums2[1] = 2相等，肉眼观察可以得到 dp[2][1] = 2;。

dp[1][2]表示在nums1[0:1] = {0, 1}与nums2[0:2] = {1, 2, 3}中找公共子串，同时要求子串的最后一个元素必须与nums1[1] = 1与nums2[2] = 3相等。这是一个矛盾的命题，不可能满足，因此dp[1][2] = 0;。

dp数组的递推公式：

if(nums1[i] == nums2[j]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = 0;

else {...}中的情况刚刚解释过，而当nums1[i] == nums2[j]时证明我们最长的公共子串长度可以在之前的基础上再加1，请大家结合下面的图片仔细理解一下这句话。

1.2.2 dp数组初始化：

可以看到递推方向是左上到右下，因此我们需要初始化的元素有：

对于dp[0][j]来说，当nums2[j] = nums1[0]时，对应的dp[0][j]需要置1。
对于dp[i][0]来说，当nums1[i] = nums2[0]时，对应的dp[i][0]需要置1。
这里其实很好理解，假设初始化dp[0][j]时，结合dp定义这个时候nums1只有一个元素nums1[0]在区间内，因此当出现nums2[j] = nums1[0]，就证明最大子数组长度为1。

1.3 示例代码

1.3.1 标准方法

下面就是参考代码。

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {// dp初始化vector<vector<int>> dp(nums1.size(), vector<int>(nums2.size(), 0));int ret = 0;	// 定义一个计数器，初始时 ret=0for(int j = 0; j < nums2.size(); j++) {if(nums1[0] == nums2[j]) { dp[0][j] = 1;ret = 1;	// 至少有一个元素相等}}for(int i = 0; i < nums1.size(); i++) {if(nums2[0] == nums1[i]) {dp[i][0] = 1;ret = 1;	// // 至少有一个元素相等}}// 递推for(int i = 1; i<nums1.size(); i++) {for(int j = 1; j < nums2.size(); j++) {if(nums1[i] == nums2[j]) dp[i][j] = dp[i-1][j-1] + 1;ret = std::max(ret, dp[i][j]);}}return ret;}
};

注意:
（1）这道题返回值看似不是dp，但是实际上ret就是在记录dp中的最大值，因此这个题目中dp与结果是强相关的。
（2）这道题在初始化dp时就把所有元素默认为0，因此在递推时不需要写else分支。

1.3.2 简化初始化流程

在上面的代码中我们发现初始化是一个比较麻烦的事情，对于做过动态规划的朋友们都会有一个经验，就是把dp数组的大小设计的比数据量多一个，暨n个数据，dp数组则设计为n+1。通过这种方式可以简化dp初始化步骤。、
看下面的代码：

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size()+1, vector<int>(nums2.size()+1, 0));int ret = 0;for(int i = 1; i<=nums1.size(); i++) {for(int j = 1; j <= nums2.size(); j++) {if(nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;ret = std::max(ret, dp[i][j]);}}return ret;}
};

这里我们给dp数组多留出来了一个位置，保证dp数组左上方向全部为0，这样我们就不需要对边界初始化了。

同步修改一下dp的定义：
这里定义dp[i][j]为：在nums1的索引[0, i-1] 与nums2的索引[0, j-1]内寻找公共子串，公共子串的最后一个元素必须与nums1[i-1]与nums2[j-1]相等，子串的长度为dp[i][j]。

其余的推导全部一致，大家一定要自己写一遍，后面我都会用这种简化的方法。

2、公共子序列

2.1 题目描述

最长公共子序列 - 力扣
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。
一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列，因为c与e的相对顺序发生改变。
两个字符串的公共子序是这两个字符串所共同拥有的子序列。

2.2 题目分析

读题，发现这道题要求我们求公共子序列，不要求连续。
这道题即使用暴力解法，思路是通过回溯把text1的所有可能的子序列放入unordered_set中，再把text2所有可能的子序列找出来在哈希表中查询。如果题目要求我们输出最长子串内的每个元素，那我们只能这么做。但是这道题只要求我们输出长度。

2.2.1 dp数组的定义

我刚刚说过，两个字符串的动规，需要二维dp数组。
定义dp[i][j]为：text1在[0, i-1]范围内，text2在[0, j-1]范围内的最大公共子序列长度。

dp的递推关系为：

if(text1[i-1] == text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = std::max(dp[i-1][j], dp[i][j-1];

看过最长回文子序列那篇文章的同学对这个应该不陌生。这里解释一下：
（1）当text1[i-1] == text2[j-1]时，公共子序列长度应该在之前的记录的值的基础上加1，之前的值是什么呢，当然是dp[i-1][j-1]了。
（2）当text1[i-1] != text2[j-1]时，证明text1[i-1] 与text2[j-1]元素不同，公共子序列的长度应该为之前记录的最大值，但是这种情况下这里之前记录的最大值是什么呢？
有同学直接默认为dp[i-1][j-1]，这是表示text1[i-2] == text2[j-2]，但是我们不妨是靠一下，虽然text1[i-1] != text2[j-1]，但是有没有可能存在text1[i-2] == text2[j-1]或者text1[i-1] == text2[j-2]的情况呢？所以说我们寻找的最大值应该是dp[i-1][j]与dp[i][j-1]中更大的那一个。

**注意：**对于字符串问题的dp数组定义方式有两种，这两种定义方式的区别是：是否明确要求以对应索引元素结尾。结题时很难直接确定使用哪一种方式，还是要靠经验，大家不妨也按照另一种方式设计一下：
定义dp[i][j]为：text1在[0, i-1]范围内，text2在[0, j-1]范围内的最大公共子序列长度，且最长公共子序列必须以text1[i-1]与text2[j-1]所标识的共同元素结尾
这种定义下，dp的递推公式为：

if(text1[i-1] == text2[j-1]) dp[i][j] = func(i-1, j-1) + 1;
else dp[i][j] = 0;

我们需要一个dp数组在[0 … i-1] and [0 … j-1]范围内的最大值，用函数func来返回。
这么一看这种方法更加困难。

2.2.2 dp数组的初始化

如何初始化我在上文的公共子串中讲述的很明白了，我们扩充了dp数组的大小，实现了简化的初始化步骤。这里我就不再赘述了。

1.3 示例代码

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text2.size()+1, vector<int>(text1.size()+1, 0));// int ret = 0; 这种dp定义方式下不需要记录最大值，dp本身就是最大值for(int i = 1; i <= text2.size(); i++) {for(int j = 1; j <= text1.size(); j++) {if(text1[j-1] == text2[i-1]) dp[i][j] = dp[i-1][j-1] + 1;else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);// ret = std::max(ret, dp[i][j]);}}return dp.back().back();}
};

碎碎念：
我刚刚给大家说了dp数组的定义问题，我们在最终结果输出时，可以明确看出两种方式的区别，在当前我们定义的模式下，最右下角的元素就是我们要的结果。
而在另一种定义方式下（强制要求尾部元素），我们需要在dp数组内寻找最大值。
这里没有什么好办法来进行很好的区分，需要大家结合经验来判断。

3 拓展

3.1 回文串长度的另一种解法

题目链接：最长回文子序列 - 力扣

不知道这道题的可以去看我之前的文章：动态规划算法：字符串类问题（1）回文串

我在这篇文章里说到，设计到两个字符串的动态规划问题都需要二维dp数组。对于回文串，我们仅在一个字符串上进行判断，却仍然使用了二维dp数组，不知道大家有没有一些思考。
回文串的定义是正着读与反着读都一样的字符串，所以我们是在两个方向上判断一个字符串，所以其实还是两个字符串，所以dp数组也要用二维。

结合上面的文字描述，大家很有可能想出一个诡异的做法。回文串的定义是正着读与反着读都一样的字符串。
我们将字符串逆序去找公共子序列，是不是可以从另一个方向上解决这个问题呢？

直接给代码：

class Solution {int findLength(string& nums1, string& nums2) {vector<vector<int>> dp(nums1.size()+1, vector<int>(nums2.size()+1, 0));int ret = 0;for(int i = 1; i<=nums1.size(); i++) {for(int j = 1; j <= nums2.size(); j++) {if(nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);ret = std::max(ret, dp[i][j]);}}return ret;}public:int longestPalindromeSubseq(string& s) {string s2 = s;reverse(s2.begin(), s2.end());return findLength(s, s2);}
};

这里直接逆序字符串，并去找最长公共子序列，上面的私有化方法就是我们这篇文章第二部分讲的公共子序列的函数接口。

4 小结

这篇文章里我们继续拓展了字符串类的动态规划问题。
我们进一步加深了二维dp数组在字符串问题中的使用，并总结了一些规律。
我们对回文子序列长度提出了另一种解法。
这类问题会涉及到一些变种，由于篇幅原因我会在下一篇文章中进行讲解。
感谢大家的阅读，希望大家有所收获。