动态规划经典模型：双数组问题的通用解决框架与实战

41.最长公共子序列

最长公共子序列
给定两个字符串 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 <= 1000
• text1 和 text2 仅由小写英文字符组成。

选取第一个字符串[0,i]区间以及第二个字符串[0,j]区间作为研究对象

dp[i] [j]表示：s1的[0,i]区间以及s2的[0,j]区间内所有的子序列中，最长公共子序列的长度

如果两个字符串的i和j位置的字符都是相等的，那么我们就直接去(i-1,j-1)区间去找，那么此时的长度就是dp[i-1] [j-1]+1

但是如果不相等的话，那么是存在三种情况的，因为i和j不相等，那么我们就不能同时带上这两个位置
那么我们是可以搜索dp[i-1] [j] 和dp[i] [j-1] 和dp[i-1] [j-1]这三种情况的
在这三种情况中求出最大值就行了

但是我们的dp[i-1] [j-1]是被另外两种状态所包含的
所以我们这里是存在重复的情况的，但是我们这里是求最长的公共子序列的，所以不漏就行了，重复的话是无所谓的

初始化的话，引入空串的概念之后，会方便我们的初始化

我们在两个字符串的前面加上空字符，那么就可以让下标直接进行映射操作

返回值的话我们就直接返回dp[m] [n]

class Solution{public:int longestCommonSubsequence(string s1, string s2){int m=s1.size();int n=s2.size();vector<vector<int>>dp(m+1,vector<int>(n+1));//规格是(m+1,n+1)的矩阵，初始化的话里面默认是0for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){//两个结尾的字符是相同的，那么我们去[i-1][j-1]这个区间去找最长的子序列if(s1[i-1]==s2[j-1])//因为我们阔了一行和一列，所以我们是需要进行-1操作的才能找到原来的字符的dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);//两种情况的最大值}}return dp[m][n];}};

这种写法是我们没有在字符串前面加上一个空格，这样映射的话我们得-1才能找到原始的字符

那么下面的写法我们就在两个字符串前面加上一个字符

class Solution{public:int longestCommonSubsequence(string s1, string s2){int m=s1.size();int n=s2.size();s1=" "+s1,s2=" "+s2;vector<vector<int>>dp(m+1,vector<int>(n+1));//规格是(m+1,n+1)的矩阵，初始化的话里面默认是0for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){//两个结尾的字符是相同的，那么我们去[i-1][j-1]这个区间去找最长的子序列if(s1[i]==s2[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[m][n];}};

我们直接进行在空格后面进行字符串的追加操作，利用’+’

42.不相交的线

不相交的线
在两条独立的水平线上按给定的顺序写下 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

最长公共子序列

dp[i] [j]表示：在n1里面的[0,i]区间以及n2里面的[0,j]区间里面的所有子序列中，最长公共子序列的长度

class Solution {public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2){int m=nums1.size(),n=nums2.size();vector<vector<int>>dp(m+1,vector<int>(n+1));//将这个矩阵初始化为0for(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;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}return dp[m][n];}};

这个题就是求最长的公共子序列问题

43.不同的子序列

不同的子序列
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

示例 1：

输入： s = “rabbbit”, t = “rabbit”
输出：**3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。

示例 2：

输入： s = “babgbag”, t = “bag”
输出：5
解释
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。

提示：

• 1 <= s.length, t.length <= 1000
• s 和 t 由英文字母组成

dp[i] [j]表示：s字符串[0,j]区间内所有的子序列中，有多少个t字符串[0,i]区间内的子串
子串是连续的
子序列是不连续的

第一行就是当t是空串的话，在s中肯定是存在1个的
但是第一列的话，如果s是空的话，那么除非t是空的才是一个1，其他的都是0

返回值是dp[m] [n]

class Solution{public:int numDistinct(string s, string t){int m=t.size(),n=s.size();vector<vector<double>>dp(m+1,vector<double>(n+1));for(int j=0;j<=n;j++)dp[0][j]=1;//将第一行初始化为1for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){//我们要考虑不使用 s 的第 j 个字符（即 s[j - 1]）来进行匹配的情况。dp[i][j]+=dp[i][j-1];//不包含s[j]的情况if(s[j-1]==t[i-1])dp[i][j]+=dp[i-1][j-1];}}return dp[m][n];}};

44.通配符匹配

通配符匹配
给你一个输入字符串 (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 <= 2000
• s 仅由小写英文字母组成
• p 仅由小写英文字母、'?' 或 '*' 组成

dp[i] [j]表示：p[0,j]区间内的子串能否匹配s的[0,i]区间

当我们的s[i]和p[j]相等匹配了的话，那么我们还需要看s的(0,i-1)区间和p的(0,j-1)区间是否匹配，就是dp[i-1] [j-1]是否为true

如果p[j]是问号的话，那么我们就将s[i]消掉了，那么我们只需要看dp[i-1] [j-1]是否为true

如果j位置是* 的话，那么我们如果匹配的是s的空串的话，那么我们就得看dp[i] [j-1]是否为true了

现在的话我们就得想办法将这么多的状态进行优化操作

初始化的话
引入空串

class Solution{public:bool isMatch(string s, string p){int m=s.size(),n=p.size();s=" "+s,p=" "+p;//保证dp数组下标和原始数组下标进行一个对应的操作vector<vector<bool>>dp(m+1,vector<bool>(n+1));//初始化默认是false//初始化操作dp[0][0]=true;//空字符串和空模式是匹配的。这个是基础的边界情况。for(int j=1;j<=n;j++)//字符串和模式的匹配情况，只有*才能匹配空字符串，如果不是空字符串的话，那么匹配的结果就是falseif(p[j]=='*')dp[0][j]=true;//当这个位置是*的时候，我们第一行初始化为trueelse break;//如果碰到的不是*的话，那么我们直接退出，默认初始化为false//填表for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(p[j]=='*'){dp[i][j]=dp[i-1][j]||dp[i][j-1];//如果 dp[i-1][j] 为 true，意味着 * 匹配了一个字符；//如果 dp[i][j-1] 为 true，意味着 * 匹配了零个字符。}else //剩下的两种情况{//如果这个最后一个符号是问号或者最后的两个字符串最后一个字符都是相等的dp[i][j]=(p[j]=='?'||s[i]==p[j])&&dp[i-1][j-1]==true;//只要这两种情况有一种成立的话，并且加上后面的dp[i-1][j-1]==true这个条件的话,如果都成立的话//dp[i][j]就等于true//这个代码就是将p[j]是普通字符和p[j]='?'的情况都进行了一个包括的操作}}}return dp[m][n];}};

如果是* 的话，那么我们就一直和字符进行匹配，或者匹配空字符

dp[i][j]=(p[j]=='?'||s[i]==p[j])&&dp[i-1][j-1]==true;这个的话就是j位置是字符或者是问号的情况的
将这两种情况进行一个归并的操作

45.正则表达式匹配

正则表达式匹配

给你一个字符串 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 <= 20
• 1 <= p.length <= 20
• s 只包含从 a-z 的小写字母。
• p 只包含从 a-z 的小写字母，以及字符 . 和 *。
• 保证每次出现字符 * 时，前面都匹配到有效的字符

dp[i] [j]表示：p[0,j]区间内的子串是否能够匹配s[0,i]区间内的子串

我们是可以根据p的最后一个字符进行判断，最后一个字符是存在三种情况的
第一种就是26个字符
第二种就是 .
第三种就是 *

当p[j]是小写字母的时候
只要p[j]== s[i] 并且dp [i-1] [j-1]== true 的话，那么dp[i] [j]就等于true

如果是 . 的话，那么我们和一个字符进行匹配，那么我们只需要检查dp[i-1] [j-1]是否为true就行了

如果是* 的话

初始化操作：引入空串
dp[ 0] [0]初始化为true，因为此时的s和p都是空的
dp[1] [0]到do[n-1] [0]都初始化为false，因为我们的p是空的，不能与s进行匹配操作
第一行的话，第一个格子就是上面的dp[ 0] [0]，初始化为true
第一行是需要做判断的，判断偶数位置是否为*

返回的是dp[m] [n]
如果不懂的话可以看上面的流程图就行了

class Solution{public:bool isMatch(string s, string p){int m=s.size(),n=p.size();s=" "+s,p=" "+p;//默认初始化为falsevector<vector<bool>>dp(m+1,vector<bool>(n+1));//规模是(m+1,n+1)//初始化操作dp[0][0]=true;//因为此时我们是需要初始化第一行的，dp[0][j]，就是说s是空的，但是p不是空的，所以我们是需要堆p进行判断操作for(int j=2;j<=n;j+=2)//每次往后面移动两位，看看偶数位上是否为*if(p[j]=='*')dp[0][j]=true;//只要偶数位置上是*的话，那么我们就可以和前面一个位置上的字符与s这个空字符串进行匹配的操作了else break;//不是*的话直接跳出去，因为其他的都是false了//填表for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(p[j]=='*'){//j位置是*的话，dp[i][j-2]就是一个字符和*然后匹配到s的空字符//或者前面的字符是'.'或者j-1位置和i位置的字符相等，那么我们就匹配一个并且保留*，然后检查dp[i-1][j]是否为true就行了dp[i][j]=dp[i][j-2]||(p[j-1]=='.'||p[j-1]==s[i])&&dp[i-1][j];}else//就是这个位置上是普通字符和 '.'的两种情况{//如果i和j位置的字符相等，或者是j位置的是'.' ,就是最后一个字符能匹配的情况下，那么我们就得看下dp[i-1][j-1]的位置了dp[i][j]=(p[j]==s[i]||p[j]=='.')&&dp[i-1][j-1]==true;}}}return dp[m][n];}};

46.错字符串

交错字符串
给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

• s = s1 + s2 + ... + sn
• t = 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 <= 100
• 0 <= s3.length <= 200
• s1、s2、和 s3 都由小写英文字母组成

进阶： 您能否仅使用 O(s2.length) 额外的内存空间来解决它?

dp[i] [j]表示：s1中[1,i]区间内的字符串以及s2中[1,j]区间内的字符串能否拼接凑成s3[1,i+j]区间内的字符串
就两种情况，一种是s3最后一个字符是i位置的
一种是s3最后一个字符是j位置的

初始化：
(0,0)位置初始化为true，因为两个串都是空的
第一行的话就是说明我们的s1是空的，s2不是空的，但是情况的话我们是需要进行判断的，我们进行两个字符串的遍历，只要对应位置元素是相同的，那么这个位置就是true，如果第一次出现位置元素不同的话，那么这个结果就是false了

第一列的话就是说明我们的s1不是空的，s2是空的，判断方式同上

返回值的话我们直接返回dp[m] [n]就行了

class Solution{public:bool isInterleave(string s1, string s2, string s3){int m=s1.size(),n=s2.size();if(m+n!=s3.size())return false;//特殊情况s1=" "+s1,s2=" "+s2,s3=" "+s3;vector<vector<bool>>dp(m+1,vector<bool>(n+1));dp[0][0]=true;//第一个位置，两个串都是空串的情况下//遍历第一行.s1是空的，但是s2不是空的，我们需要判断此时的s2是否等于s3了for(int j=1;j<=n;j++){if(s2[j]==s3[j])dp[0][j]=true;else break;//如果字符不相等的话，我们直接break,剩下的都是false就行了}//初始化第一列,此时的s2是空的，那么我们就需要判断s1是否和s3对应元素相等了for(int i=1;i<=m;i++){if(s1[i]==s3[i])dp[i][0]=true;else break;//如果字符不相等的话，我们直接break,剩下的都是false就行了}//开始进行填表for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j]=(s1[i]==s3[i+j]&&dp[i-1][j]==true)//这个就是s1的i位置元素等于s3的i+j的位置，并且dp[i-1][j]还是true||(s2[j]==s3[i+j]&&dp[i][j-1]==true);}}return dp[m][n];}};

47.两个字符串的最小ASCII删除和

两个字符串的最小ASCII删除和
给定两个字符串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 <= 1000
• s1 和 s2 由小写英文字母组成

将题目进行转换：求两个字符串里面的公共子序列里面，ASCII值的最大和

dp[i] [j]表示：s1的[0,i]区间以及s2的[0,j]区间内的所有子序列里面，公共子序列的ASCII最大和

根据最后一个位置的状况，分情况进行讨论，求出下面四种情况的最大值就行了

最后一种情况可以不用求，因为第二种情况和第三种情况是包含最后一种情况的

第一行就是说s1是空的，那就找不到公共子序列了，那么斗初始化为0就行了

第一列一样，都初始化为0就行了

class Solution {public:int minimumDeleteSum(string s1, string s2){int m=s1.size(),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]，要么就是没有s1[i]，有s2[j]//两种情况求个最大值就行了dp[i][j]=max(dp[i-1][j],dp[i][j-1]);if(s1[i-1]==s2[j-1])//这里我们是需要进行映射的，因为我们扩展了一行和一列的dp[i][j]=max(dp[i][j],dp[i-1][j-1]+s1[i-1]);//我们这里加个s1[i]就行了，因为s2[j]==s1[i]。并且我们这里的s1[i-1]这里的-1就是为了找到原数组的字符元素}}//返回之前我们需要先统计两个字符串的ASCIIint sum=0;//计算两个字符串的ASCII总和for(auto s:s1)sum+=s;for(auto s:s2)sum+=s;//减去公共子序列的ASCII，就可以得到我们的删除字符的 ASCII 值的最小和了。return sum-dp[m][n]-dp[m][n];//因为这个ASCII是从原来的两个字符串中剥离了n个两个相同的字符的，所以我们这里是需要乘以二的}};

48.最长重复子数组

最长重复子数组
给两个整数数组 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

dp[i] [j]表示：nums1中以i位置元素为结尾的所有子数组以及nums2中以j位置元素为结尾的所有子数组中，最长重复子数组的长度

第一行初始化为0，因为第一行表示的是第一个数组是空的，那么我们就找不到重复子数组了
第一列也是一样的，都初始化为0

class Solution {public:int findLength(vector<int>& nums1, vector<int>& nums2){int m=nums1.size(),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++){//如果nums1[i]!=nums2[j]的话，那么dp[i][j]=0,我们是不需要管的//下面是两个位置的元素相等，这里我们-1了，因为我们多加了一行和一列，所以需要进行-1映射坐标了if(nums1[i-1]==nums2[j-1]){dp[i][j]=dp[i-1][j-1]+1;//加上当前的位置的长度ret=max(ret,dp[i][j]);}}}return ret;}};