算法沉淀——动态规划之两个数组的 dp（下）（leetcode真题剖析）

01.正则表达式匹配

题目链接：https://leetcode.cn/problems/regular-expression-matching/

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

• '.' 匹配任意单个字符
• '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

示例 1：

输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
1
2
3

示例 2:

输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
1
2
3

示例 3：

输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。 
1
2
3

提示：

• 1 <= s.length <= 20
• 1 <= p.length <= 20
• s 只包含从 a-z 的小写字母。
• p 只包含从 a-z 的小写字母，以及字符 . 和 *。
• 保证每次出现字符 * 时，前面都匹配到有效的字符

思路

在处理字符串匹配的动态规划问题时，通常按照以下步骤进行：

1. 状态表达：

   • 选取第一个字符串 [0, i] 区间以及第二个字符串 [0, j] 区间作为研究对象，结合题目的要求定义状态表达。
   • 在这道题中，我们定义状态表达为 dp[i][j]，表示字符串 p 的 [0, j] 区间和字符串 s 的 [0, i] 区间是否可以匹配。

2. 状态转移方程：

   • 根据最后一个位置的元素，结合题目要求，进行分类讨论：
     • 当 s[i] == p[j] 或 p[j] == '.' 时，两个字符串匹配上了当前的一个字符，只能从 dp[i-1][j-1] 中看当前字符前面的两个子串是否匹配，继承上个状态中的匹配结果，dp[i][j] = dp[i-1][j-1]。
     • 当 p[j] == '*' 时，匹配策略有两种选择：
       • 一种选择是：p[j-1]* 匹配空字符串，相当于这两个字符都匹配了一个寂寞，直接继承状态 dp[i][j-2]，dp[i][j] = dp[i][j-2]。
       • 另一种选择是：p[j-1]* 向前匹配 1 ~ n 个字符，直至匹配上整个 s 串。相当于从 dp[k][j-2] (0 < k <= i 且 s[k]~s[i] = p[j-1]) 中所有匹配情况中，选择性继承可以成功的情况，dp[i][j] = dp[k][j-2] (0 < k <= i)。
     • 当 p[j] 不是特殊字符且不与 s[i] 相等时，无法匹配。综上，状态转移方程为：
       • 当 s[i] == p[j] 或 p[j] == '.' 时：dp[i][j] = dp[i-1][j-1]。
       • 当 p[j] == '*' 时，状态转移方程为：dp[i][j] = dp[i][j-2] || dp[i-1][j]。

3. 初始化：

   • dp 数组的值表示是否匹配，初始化整个数组为 false。
   • 由于需要用到前一行和前一列的状态，初始化第一行和第一列。
     • dp[0][0] 表示两个空串是否匹配，初始化为 true。
     • 第一行表示 s 为空串， p 串全部字符表示为 ".*" 或 "任一字符*"，此时相当于空串匹配上空串，将所有前导为 "任一字符*" 的 p 子串和空串的 dp 值设为 true。
     • 第一列表示 p 为空串，不可能匹配上 s 串，跟随数组初始化即可。

4. 填表顺序：

   • 从上往下填每一行，每一行从左往右。

5. 返回值：

   • 根据状态表达，返回 dp[m][n] 的值。

代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int m=s.size(),n=p.size();
        s=" "+s,p=" "+p;
        vector<vector<bool>> dp(m+1,vector<bool>(n+1));
        dp[0][0]=true;
        for(int i=2;i<=n;i+=2)
            if(p[i]=='*') dp[0][i]=true;
            else break;

        for(int i=1;i<=m;++i)
            for(int j=1;j<=n;++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[m][n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

02.交错字符串

题目链接：https://leetcode.cn/problems/interleaving-string/

给定三个字符串 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
1
2

示例 2：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false
1
2

示例 3：

输入：s1 = "", s2 = "", s3 = ""
输出：true
1
2

提示：

• 0 <= s1.length, s2.length <= 100
• 0 <= s3.length <= 200
• s1、s2、和 s3 都由小写英文字母组成

思路

1. 状态表达：
   • 对于两个字符串的动态规划问题，首先考虑选取第一个字符串的 [0, i] 区间和第二个字符串的 [0, j] 区间作为研究对象。
   • 定义状态表达 dp[i][j]，表示字符串 s1 中 [1, i] 区间内的字符和字符串 s2 中 [1, j] 区间内的字符是否能够交错组成字符串 s3 中 [1, i + j] 区间内的字符。
2. 状态转移方程：
   • 根据两个区间上的最后一个字符，进行分类讨论：
     • 如果 s3[i + j] = s1[i]，说明交错后的字符串的最后一个字符和 s1 的最后一个字符匹配了。这时，需要判断整个字符串是否能够交错组成，即 dp[i][j] = dp[i - 1][j]。
     • 如果 s3[i + j] = s2[j]，说明交错后的字符串的最后一个字符和 s2 的最后一个字符匹配了。这时，需要判断整个字符串是否能够交错组成，即 dp[i][j] = dp[i][j - 1]。
     • 如果两者的末尾字符都不等于 s3 最后一个位置的字符，说明不可能是两者的交错字符串，dp[i][j] 保持不变。
3. 初始化：
   • 初始化第一个位置，dp[0][0] = true，因为空串与空串能够构成空串。
   • 初始化第一行，dp[0][j]，表示 s1 是空串，需要判断与 s2 的交错情况。如果 s2[j - 1] == s3[j - 1] 且 dp[0][j - 1] 为真，则 dp[0][j] = true。
   • 初始化第一列，dp[i][0]，表示 s2 是空串，需要判断与 s1 的交错情况。如果 s1[i - 1] == s3[i - 1] 且 dp[i - 1][0] 为真，则 dp[i][0] = true。
4. 填表顺序：
   • 从上往下逐行填表，每一行从左往右。
5. 返回值：
   • 根据状态表达 dp[m][n] 的值，其中 m 和 n 分别是 s1 和 s2 的长度，判断是否能够交错组成字符串 s3。

代码

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m=s1.size(),n=s2.size();
        if(s3.size()!=m+n) return false;
        s1=" "+s1,s2=" "+s2,s3=" "+s3;
        vector<vector<bool>> dp(m+1,vector<bool>(n+1));

        dp[0][0]=true;
        for(int i=1;i<=n;++i) 
            if(s2[i]==s3[i]) dp[0][i] = 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++)
                dp[i][j]=(s1[i]==s3[i+j]&&dp[i-1][j])||(s2[j]==s3[i+j]&&dp[i][j-1]);

        return dp[m][n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

题目链接：https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/

给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。

示例 1:

输入: s1 = "sea", s2 = "eat"
输出: 231
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
在 "eat" 中删除 "t" 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。
1
2
3
4
5

示例 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 的结果，比答案更大。
1
2
3
4
5
6

提示:

• 0 <= s1.length, s2.length <= 1000
• s1 和 s2 由小写英文字母组成

思路

1. 状态表达：

   • dp[i][j] 表示字符串 s1 的 [0, i] 区间以及字符串 s2 的 [0, j] 区间内的所有的子序列中，公共子序列的 ASCII 最大和。

2. 状态转移方程：

   • 根据最后一个位置的元素，进行情况讨论：

     • 如果 s1[i] == s2[j]，说明当前字符可以被加入到公共子序列中，此时 dp[i][j] = dp[i - 1][j - 1] + s1[i]。

     • 如果

       s1[i] != s2[j]
       1

       ，此时有三种可能：

       • 在 s1 的 [0, i - 1] 区间以及 s2 的 [0, j] 区间内找公共子序列的最大和，即 dp[i][j] = dp[i - 1][j]。
       • 在 s1 的 [0, i] 区间以及 s2 的 [0, j - 1] 区间内找公共子序列的最大和，即 dp[i][j] = dp[i][j - 1]。
       • 在 s1 的 [0, i - 1] 区间以及 s2 的 [0, j - 1] 区间内找公共子序列的最大和，即 dp[i][j] = dp[i - 1][j - 1]。

     • 由于前两种情况包含了第三种情况，因此只需考虑前两种情况下的最大值。

3. 初始化：

   • 引入空串后，扩大了状态表的规模，方便初始化。
   • 需要注意下标的映射关系以及确保后续填表的正确性。
   • 当 s1 和 s2 为空时，没有长度，所以第一行和第一列的值初始化为 0。

4. 填表顺序：

   • 从上往下逐行填表，每一行从左往右。

5. 返回值：

   • 先找到 dp[m][n]，即最大公共 ASCII 和。
   • 统计两个字符串的 ASCII 码和 sum。
   • 返回 sum - 2 * dp[m][n]。

代码

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));

        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++){
                dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
                if(s1[i-1]==s2[j-1]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+s1[i-1]);
            }
        int sum=0;
        for(auto s:s1) sum+=s;
        for(auto s:s2) sum+=s;
        return sum-dp[m][n]*2;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

04.最长重复子数组

题目链接：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/

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

示例 1：

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。
1
2
3

示例 2：

输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5
1
2

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 100

思路

1. 状态表达：
   • dp[i][j] 表示以第一个数组的第 i 位置为结尾以及第二个数组的第 j 位置为结尾时，两个数组的最长重复子数组的长度。
2. 状态转移方程：
   • 当 nums1[i] == nums2[j] 时，说明当前位置两个数组的元素相等，此时最长重复子数组的长度应该等于 1 加上除去最后一个位置时，以 i - 1, j - 1 为结尾的最长重复子数组的长度，即 dp[i][j] = 1 + dp[i - 1][j - 1]。
3. 初始化：
   • 为了处理越界的情况，添加了一行和一列，使 dp 数组的下标从 1 开始。
   • 第一行表示第一个数组为空，因此没有重复子数组，所以其中的值设置为 0。
   • 第一列同理。
4. 填表顺序：
   • 根据状态转移方程，从上往下逐行填表，每一行从左往右。
5. 返回值：
   • 根据状态表达，需要返回 dp 表中的最大值。

代码

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));

        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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14