给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。示例 2：
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。示例 3：
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。提示：
1 <= text1.length, text2.length <= 1000text1和text2仅由小写英文字符组成。
解题思路
这是我们遇到的一种新的动态规划的题型，这道题也算是很经典的，基本是我们这种类型题的一个模板题！
对于这种题，我们以前的经验，也就是以某个位置结尾然后……的情况其实在这就不太灵了，虽然可以用，但是用的话其实时间复杂度甚至达到了 级别。所以我们要换一种经验方式去表示状态！
假设两个字符串，分别是 s1 和 s2，它们分别有 i 和 j 表示下标，此时我们的状态可以设为 dp[i][j] 表示在字符串 s1 的 [0, i] 区间，字符串 s2 的 [0, j] 区间内的所有子序列中，最长的公共子序列的长度。
然后就是状态转移方程，通常此类题型，我们会根据其最后一个位置的状态来分情况讨论，如下图所示：
初始化问题，其实也有很多细节，因为状态转移方程涉及到了 dp[i - 1][j]、dp[i][j - 1]、dp[i - 1][j - 1]，也就是上边、左边、左上角的位置，所以对于一个二维的 dp 表来说，最省功夫的方法就是开辟虚拟行列，对虚拟行列进行初始化！我们之前也有碰到过开辟虚拟行列，还是要遵守下面的两个要点：
- 虚拟位置的初始化要保证后面填表的正确
- 对于这道题来说，因为要求的是长度，那么只需要
初始化虚拟行列都为 0 即可，具体为什么行可以自己代入位置去验证！
- 对于这道题来说，因为要求的是长度，那么只需要
- 下标的映射关系
- 对于字符串的问题，我们只需要
在题目给的字符串的前面加上一个空格 “ ”，这个字符可以自己定，一般我们都是用添加空格！ - 这样子有什么好处呢，我们就 不用去关心下标映射关系了，因为我们开辟了虚拟行列，元素都往右下角移动了一个单位距离，那么我们在原字符串的开头添加一个自定义字符，相当于这个距离对两者来说是没有变过的！
- 对于字符串的问题，我们只需要
遍历顺序问题，因为用到了上边、左边、左上角的元素，所以我们要从上往下，从左往右遍历！
返回值问题，根据我们的状态表示可以知道，要返回的就是 dp[n][m]，为什么不是 n-1 和 m-1 呢❓❓❓注意啊，我们是开了虚拟行列的，所以往后挪了一个单元，所以不需要减一哦！
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
// 创建dp表，注意多开一行一列作为虚拟行列
int n = text1.size();
int m = text2.size();
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
// 在两个字符串前插入空格
text1.insert(text1.begin(), ' ');
text2.insert(text2.begin(), ' ');
// 从上往下，从左往右遍历
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
if(text1[i] == text2[j])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[n][m];
}
};2、不相交的线（medium）
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：
nums1[i] == nums2[j]- 且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。以这种方法绘制线条，并返回可以绘制的最大连线数。
示例 1：
输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。示例 2：
输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出：3示例 3：
输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出：2提示：
1 <= nums1.length, nums2.length <= 5001 <= nums1[i], nums2[j] <= 2000
解题思路
这道题怎么说呢，看得出与第一道题相似之处的话，那么就是秒破，看不出来的话就比较费劲了，下面画个图理解一下，以上面的例子 2 为例：
可以看出来，这道题和最长公共子序列是异曲同工之妙，只不过这道题更加的隐晦一些！那么完全就是和第一道题一样的解法模板，只不过这道题是整型数组，而不是字符串，这个都是差不多的，具体细节可以参考最长公共子序列，这里直接给出代码：
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
// 创建dp表，注意开辟了虚拟行列
int n = nums1.size();
int m = nums2.size();
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
// 在两个数组前各插入一个虚拟位置
nums1.insert(nums1.begin(), 0);
nums2.insert(nums2.begin(), 0);
// 从上往下，从左往右遍历
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
if(nums1[i] == nums2[j])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
}
}
return dp[n][m];
}
};3、不同的子序列（hard）
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。
题目数据保证答案符合 32 位带符号整数范围。
示例 1：
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit示例 2：
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag提示：
1 <= s.length, t.length <= 1000s和t由英文字母组成
解题思路
这道题之所以是困难题，其实是难在了状态表示，因为状态表示决定了状态转移方程和后续的推导是否成立，而只要状态表示我们定义对了，其实这道题瞬间就变成了简单题！
这道题是要求的是字符串 s 中的所有子序列，包含了多少个字符串 t，那么我们就不能像之前一样，把两个字符串都求它们的子序列区间，而是只对字符串 s 划分为子序列区间，而字符串 t 是划分为子串区间，因为字符串 t 一定是要连续的！
所以状态表示 可以定义为：dp[i][j] 表示在字符串 s 中的 [0, j] 区间内的所有子序列中，出现字符串 t 中的 [0, i] 区间内的子串的次数。
接下来就是状态转移方程，如下图所示：
要注意的是，当字符串 s 中的子序列末尾包括 s[j] 的时候推出来的方程 dp[i - 1][j - 1]，是不用再加一的，因为这里只不过是前面不含 s[j] 的子串符合条件之后加上了 s[j] ，那么就变成了包含 s[j] 的字符串 s 中 [0, j] 区间该子串出现的次数了，并不需要加一！
初始化问题，和之前一样，因为状态转移方程用到了左上角和上边的元素，所以我们开辟虚拟行列，减少了需要判断越界的功夫，并且我们在字符串 s 和 t 的头部都插入一个空格，具体为什么可以参考最长公共子序列那道题！但是这还不够，因为如果直接全部初始化为 0 的话，那么会影响到状态转移方程的推导！
因为我们 i 和 j 下标都是从 1 开始遍历的，也就是推导 dp[1][1] 时候，此时要累加上左上角和上边的值，如果此时 s[0] 和 t[0] 是相同的话，那么长度起码是为 1，但是我们将左上角和上边的元素都初始化为 0，那么长度还是 0，就出错了，所以我们要将 dp 表第一行都初始化为 1。
那 dp 表的第一列用不用初始化为 1 呢❓❓❓
其实是不用的！因为 dp 表第一列其实代表的是字符串 s 是空串，那么既然是空串了，肯定凑不出一个长度给字符串 t，所以dp 表的第一列只需要初始化为 0 即可！
总结一下，就是除了 dp 表第一行初始化为 1 之外，其它都初始化为 0。
遍历顺序问题，因为状态转移方程用到了左上角和上边的元素，所以从上往下，从左往右遍历。
返回值问题，根据状态表示，我们返回 dp[n][m]。其中 n 表示字符串 t 的长度，m 表示字符串 s 的长度。
💥还有一个很坑的点，题目说用 int 不会溢出，但是实际情况是会溢出的，所以我们要用 double 类型来作为 dp 表的存储类型，防止溢出！
class Solution {
public:
int numDistinct(string s, string t) {
// 创建dp表，并且开辟虚拟行列。注意元素要为double类型，因为int会溢出
int n = t.size();
int m = s.size();
vector<vector<double>> dp(n+1, vector<double>(m+1, 0));
// 初始化dp表第一行为1，其它都是0
for(int i = 0; i <= m; ++i)
dp[0][i] = 1;
// 在字符串前都插入空格
s.insert(s.begin(), ' ');
t.insert(t.begin(), ' ');
// 从上往下，从左往右遍历
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
if(s[j] == t[i])
dp[i][j] += dp[i - 1][j - 1];
dp[i][j] += dp[i][j - 1];
}
}
return dp[n][m];
}
};4、通配符匹配（hard）
给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：
'?'可以匹配任何单个字符。'*'可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。
示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。示例 2：
输入：s = "aa", p = "*"
输出：true
解释：'*' 可以匹配任意字符串。示例 3：
输入：s = "cb", p = "?a"
输出：false
解释：'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。提示：
0 <= s.length, p.length <= 2000s仅由小写英文字母组成p仅由小写英文字母、'?'或'*'组成
解题思路
这道题其实 难在状态转移方程，因为情况比较多，并且如果不对状态转移方程优化的话，时间复杂度会达到 ，如果进行优化的话则可以降到 ，下面一起来看看这道题的解法！
状态表示
首先就是 状态表示，根据这类题的 “经验 + 题目要求”，我们可以定义状态为 dp[i][j] 表示在字符串 p 的 [0, j] 区间内的子串能否匹配字符串 s 的 [0, i] 区间内的子串，true 表示能匹配，false 表示不能匹配。
状态转移方程
接下来就是最难的状态转移方程了 ，我们还是根据最后一步的状态来分情况，因为字符串 p 中的符号决定了能不能匹配字符串 s，所以我们 以字符串 p 的状态来分情况：
p[j] 是英文字母- 这种情况稍微比较简单，就是让
p[j]和s[i]比较，看看它们是否相等，如果相等的话说明两个字符串的尾是匹配的，那么此时就变成了去判断两个字符串除了尾部前的子串是否是匹配的，也就是状态dp[i - 1][j - 1]，只要它为true，那么dp[i][j]就是true，反之为false。
- 这种情况稍微比较简单，就是让
p[j] 是 ?- 这种情况比上一种情况还要简单，因为我们 不需要去判断
p[j]和s[i]是否相等，因为问号就是匹配一个字母，所以默认就是尾部匹配了，所以只需要判断dp[i - 1][j - 1]是否为 true，是的话dp[i][j]就是true，反之为 false。
- 这种情况比上一种情况还要简单，因为我们 不需要去判断
p[j] 是 *- 这种情况是最复杂的，因为星号不仅仅可以代表多个字母，还能代表一个空串，也就是下面的情况：
- 星号表示空串：既然表示空串了那么相当于 p[j] 不存在，那么就转变成去判断
p[j - 1]和s[i]的关系，也就是判断dp[i][j - 1]是否为true，是的话则为ture。 - 星号表示匹配一个字母：转变成判断
dp[i - 1][j - 1]是否成立 - 星号表示匹配两个字母：转变成判断
dp[i - 2][j - 1]是否成立 - 星号表示匹配三个字母：转变成判断
dp[i - 3][j - 1]是否成立 - ……
- 星号表示空串：既然表示空串了那么相当于 p[j] 不存在，那么就转变成去判断
- 这种情况是最复杂的，因为星号不仅仅可以代表多个字母，还能代表一个空串，也就是下面的情况：
上面的前两种情况还好，就是星号情况的时间复杂度不太乐观，因为最外层就必须有两层循环来遍历 dp 表，然后我们还得去判断星号匹配多种字母的情况，这样子 时间复杂度就达到 了，那我们就想，能不能用有限的状态来表示这些状态（也就是用一两个状态来表示这些它们）❓❓❓
答案是有办法的！
状态转移方程优化：数学替换
听到数学就起鸡皮疙瘩，其实这种替换是很简单的，只要我们找到规律，下面我们将星号表示多个字母的情况都列举出来找找规律：
所以总结下来，状态转移方程如下所示：
初始化
这道题初始化也是比较细节，因为这道题用到了 dp[i - 1][j - 1]、dp[i][j - 1]、dp[i - 1][j]，分别是左上角、左边和上边三个元素，为了防止越界问题发生，我们采用虚拟行列的方法，那么就会涉及到下面的两个问题，其实准确来说是三个问题：
-
引入空串- 引入空串是因为虚拟行列加上去之后，第一行表示的其实是字符串 s 为空的情况，而 第一列表示的是字符串 p 为空的情况
-
虚拟位置的初始化要保证后面填表的正确-
对于
dp[0][0]来说，这个位置表示的是两个字符串都是空的情况，那么肯定就是匹配的，所以要初始化为 true。 -
对于除了
dp[0][0]的第一行虚拟位置来说，表示的是字符串 s 为空的情况，那么我们就不能直接初始化了，因为此时要判断字符串 p 是否都为星号，因为星号可以表示空串，如果说出现了英文字母或者问号，那么就得在字符串 s 中出现字母，但是字符串 s 是空的，所以只要字符串 p 中出现非星号的字符，那么就初始化为 false，如果都为星号，则该位置初始化为 true。 -
对于除了
dp[0][0]的第一列虚拟位置来说，表示的是字符串 p 为空的情况，那么肯定都初始化为 false 就行，因为字符串 p 没东西能去匹配字符串 s 的子串。
-
-
下标的映射关系- 对于这种问题，我们有两种解决方法，一般来说我们选择第二种方法：
- 在填表的时候，将原字符串的下标都减一
- 在原字符串的开头添加一个空格，来达到和增加了虚拟位置的 dp 表的下标匹配的目的，就不用我们去关心下标的映射关系了，
- 对于这种问题，我们有两种解决方法，一般来说我们选择第二种方法：
遍历顺序
因为当前的 dp 值涉及到左上角、左边和右边的 dp 值，所以我们要从上往下，从左往右去遍历。
返回值
根据状态表示，我们返回 dp[n][m]。其中 n 表示字符串 s 的长度，m 表示字符串 p 的长度。
class Solution {
public:
bool isMatch(string s, string p) {
// 创建dp表
int n = s.size();
int m = p.size();
vector<vector<bool>> dp(n+1, vector<bool>(m+1, false));
// 初始化
// 1. 在原字符串开头插入空格
s.insert(s.begin(), ' ');
p.insert(p.begin(), ' ');
// 2. 初始化dp表第一行
dp[0][0] = true;
for(int j = 1; j <= m; ++j)
{
if(p[j] != '*') // 只要出现了非星号，则表示后面的子串都不匹配了，直接break
break;
dp[0][j] = true;
}
// 从上往下，从左往右遍历填表
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
if(p[j] == s[i])
dp[i][j] = dp[i - 1][j - 1];
else if(p[j] == '?')
dp[i][j] = dp[i - 1][j - 1];
else if(p[j] == '*')
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
}
}
return dp[n][m];
}
};5、正则表达式匹配（hard）
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。示例 2:
输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。示例 3：
输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。提示：
1 <= s.length <= 201 <= p.length <= 20s只包含从a-z的小写字母。p只包含从a-z的小写字母，以及字符.和*。- 保证每次出现字符
*时，前面都匹配到有效的字符
解题思路
状态表示
首先就是 状态表示，根据这类题的 “经验 + 题目要求”，我们可以定义状态为 dp[i][j] 表示在字符串 p 中 [0, j] 区间的子串，是否能匹配字符串 s 中 [0, i] 区间的子串，true 表示能匹配，false 表示不能匹配。
状态转移方程
这道题的状态比上一道题还要复杂，可以说是上一道题的加强版，但是大体思路都是差不多的，不同的是星号这次表示的匹配零个或者多个前一个元素的情况，相当于比上一道题多加了一个限制！
我们还是根据最后一步的状态来分情况，因为字符串 p 中的符号决定了能不能匹配字符串 s，所以我们 以字符串 p 的状态来分情况：
可以看到，这次因为星号需要和前面一个元素进行匹配，所以状态更加的多，但是我们可以对其进行优化一下，优化结果已经在上图的绿色文字中提到了，现在我们重新来看看优化的过程！
状态转移方程优化 -- 数学替换
状态转移方程总结
有了上面的优化之后，我们再将之前的状态转移方程进行合并一下，因为有些条件其实是可以合并到一起去处理的，但是不合并去处理的话其实会看起更加清晰一些，这里就提供两种方式的总结：
如果对状态转移方程不够熟悉，建议还是用第一种方式去解题，等到熟练了再用第二种方法去简化！
初始化
这道题大体初始化和上一道题是一样的，唯一不同的是初始化虚拟行列第一行的时候，我们不能直接去判断每个位置是否为星号而直接处理，因为这道题有限制，就是星号要跟着前面那个元素才能有效，所以我们 需要判断偶数个单位的虚拟位置上是否为星号，如果不是的话，则后面的元素包括其前面这个匹配的元素就都是 false 了！而反之为 true。
可能有人就有疑惑，为什么判断是一个 元素 + 星号 就能保证这两个虚拟位置就能匹配字符串 s 为空串时候的正确性呢❓❓❓
因为题目说了，星号和任何一个元素匹配，可以表示零个元素，这样子的话表示零个元素之后就能表示空串了！
剩下遍历顺序和返回值和上一道题一样！
class Solution {
public:
bool isMatch(string s, string p) {
// 创建dp表，并开辟虚拟行列
int n = s.size();
int m = p.size();
vector<vector<bool>> dp(n+1, vector<bool>(m+1, false));
// 初始化
// 1. 在两个字符串开头插入空格
s.insert(s.begin(), ' ');
p.insert(p.begin(), ' ');
// 2. 初始化dp表的第一行虚拟位置
dp[0][0] = true;
for(int j = 2; j <= m; j+=2)
{
if(p[j] != '*')
break;
dp[0][j - 1] = true;
dp[0][j] = true;
}
// 从上往下，从左往右遍历
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
if(p[j] == '*')
dp[i][j] = dp[i][j - 2] || ((p[j - 1] == '.' || p[j - 1] == s[i]) && dp[i - 1][j]);
else
dp[i][j] = (p[j] == s[i] || p[j] == '.') && dp[i - 1][j - 1];
}
}
return dp[n][m];
}
};6、交错字符串（medium）
给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
s = s1 + s2 + ... + snt = t1 + t2 + ... + tm|n - m| <= 1- 交错 是
s1 + t1 + s2 + t2 + s3 + t3 + ...或者t1 + s1 + t2 + s2 + t3 + s3 + ...
注意：a + b 意味着字符串 a 和 b 连接。
示例 1：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true示例 2：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false示例 3：
输入：s1 = "", s2 = "", s3 = ""
输出：true提示：
0 <= s1.length, s2.length <= 1000 <= s3.length <= 200s1、s2、和s3都由小写英文字母组成
解题思路
状态表示
虽说这道题有三个字符串，但是其实我们用 i 来表示字符串 s1 下标，而 j 来表示字符串 s2 的下标，那么字符串 s3 的下标就可以通过 i+j 来得到了！所以我们只需要一个二维的表就能表示！
根据 “经验 + 题目要求”，可以定义 dp[i][j] 表示字符串 s1 中 [0, i] 区间的字符串，与字符串 s2 中 [0, j] 区间的字符串，是否能交错拼成字符串 s3 中 [0, i+j] 区间的字符串。
状态转移方程
初始化
还是一样，防止越界我们加入虚拟行列，并且在三个题目给的字符串的开头都插入空格，这样子我们就不用关心下标问题！
而对于虚拟行列的初始化，我们要分为三个位置来讨论：
填表顺序
因为用到左边和上边的 dp 值，所以要从上往下，从左往右遍历！
返回值
根据状态表示，就是返回 dp[m][n]。
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int m = s1.size();
int n = s2.size();
if(m + n != s3.size())
return false;
// 创建dp表，开辟虚拟行列
vector<vector<int>> dp(m+1, vector<int>(n+1, false));
// 初始化
// 1. 向原字符串开头插入空格
s1 = " " + s1;
s2 = " " + s2;
s3 = " " + s3;
// 2. 初始化虚拟行列 -- 注意这里第一行代表s1为空，判断的是s2和s3；而第一列则相反
dp[0][0] = true;
for(int j = 1; j <= n; ++j) // 遍历第一行
{
if(s2[j] == s3[j])
dp[0][j] = true;
else
break;
}
for(int i = 1; i <= m; ++i) // 遍历第一列
{
if(s1[i] == s3[i])
dp[i][0] = true;
else
break;
}
// 从上往下，从左往右填表
for(int i = 1; i <= m; ++i)
{
for(int j = 1; j <= n; ++j)
{
if((s3[i + j] == s1[i] && dp[i - 1][j] == true) ||
(s3[i + j] == s2[j] && dp[i][j - 1] == true))
{
dp[i][j] = true;
}
}
}
return dp[m][n];
}
};7、两个字符串的最小ASCII删除和（medium）
给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。
示例 1:
输入: s1 = "sea", s2 = "eat"
输出: 231
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
在 "eat" 中删除 "t" 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。示例 2:
输入: s1 = "delete", s2 = "leet"
输出: 403
解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，
将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。提示:
0 <= s1.length, s2.length <= 1000s1和s2由小写英文字母组成
解题思路
状态表示 -- 正难则反
这道题大多数的思路都是直接去找两个字符串的 ASCII 值的最小和，但是这样子其实比较复杂，因为我们不仅仅要关心最小和，而且要关心删除字符的问题，还有如何去保证其最后是会相等的问题。
但是其实我们可以转变一下思路，反着来，下面举个例子：
可以看到其中第二个删除方案得到的结果的 ASCII 值是最大的，那么我们仔细一想，我们要求的是删除字符的最小和，那么得到的不就是最后结果的最大和吗，对不对！
所以我们正难则反，只需要去求这两个字符串的最长公共子序列中 ASCII 值最大的那个组合即可！
然后用字符串 s1 和 s2 减去这个最大的 ASCII 值，得到两个字符串剩下的 ASCII 就是它们要删除的最小 ASCII 值的和！
所以最后状态表示为：dp[i][j] 表示字符串 s1 中 [0, i] 区间以及字符串 s2 中 [0, j] 区间的所有子序列中，公共子序列的最大 ASCII 值。
状态转移方程
初始化
初始化 dp 表的时候，为了防止越界，我们开辟虚拟行列，并且都初始化为 0 即可！因为状态表示是要求 ASCII 值，而为了保证后面填表的正确性，我们初始化它们为 0 就行了！
并且我们也不需要对原字符串的开头插入空格，因为对于这道题来说没方便多少，注意下标的映射关系就行！
遍历顺序
从上往下，从左往右遍历！
返回值
因为我们要的是删除字符的最小 ASCII 值的和，所以我们要用两个字符串总的 ASCII 值的和，去减掉我们算出来的公共子序列的最大 ASCII 值的和，注意要减两次，因为两个字符串都包含这个公共子序列！
class Solution {
public:
int minimumDeleteSum(string s1, string s2) {
// 创建dp表，开辟虚拟行列，并初始化为0
int m = s1.size();
int n = s2.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
// 从上往下，从左往右遍历
for(int i = 1; i <= m; ++i)
{
for(int j = 1; j <= n; ++j)
{
// s1[i]和s2[j]不相等的情况
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
// s1[i]和s2[j]相等的情况 -- 注意这里与原字符串的下标映射关系
if(s1[i - 1] == s2[j - 1])
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + s1[i - 1]);
}
}
// 计算出s1和s2字符串的总ascii值
int sum = 0;
for(auto& e : s1)
sum += e;
for(auto& e : s2)
sum += e;
// 最后返回总ascii值减去两次最大公共子序列ascii值的结果
return sum - 2*dp[m][n];
}
};8、最长重复子数组（medium）
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5提示：
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 100
解题思路
状态表示
这道题相对来说比较简单，是数组的问题，只不过是两个子数组！
根据 “经验+题目要求”， 可以定义状态为 dp[i][j] 表示 nums1 中以 i 结尾的子数组，以及 nums2 中以 j 结尾的子数组中的最长公共子数组！
状态转移方程
这道题的方程比较简单，因为想一下，只有当 nums1[i] == nums2[j] 的时候，才有意义，不然的话根据该状态表示可以得到两个子数组的结尾不相等的话，那么就是 0，这个我们可以在初始化的时候就去初始化为 0。
而如果 nums1[i] == nums2[j] 了，此时说明长度起码为 1，那么就要用这个 1 加上前面可能存在的最长公共子数组，其存放在 dp[i - 1][j - 1] 中，所以状态转移方程就是 dp[i][j] = dp[i - 1][j - 1] + 1。
初始化
我们可以开辟虚拟行列，然后初始化为 0 即可，这样子不会影响到后面的填表正确性！
填表顺序
从上往下，从左往右遍历即可！
返回值
因为最大长度可能不是出现在 dp[m][n] 中，所以我们要用变量去记录下途中出现的最大长度，最后返回它即可！
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
// 创建dp表，开辟虚拟行列并初始化为0
int m = nums1.size();
int n = nums2.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
// 从上往下，从左往右填表
int ret = 0;
for(int i = 1; i <= m; ++i)
{
for(int j = 1; j <= n; ++j)
{
if(nums1[i - 1] == nums2[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
ret = max(ret, dp[i][j]);
}
}
return ret;
}
};