动态规划之两个数组的 dp（下）

正则表达式匹配

题目：正则表达式匹配

思路

• 状态表示：选第一个字符串的 [0, i]区间和第二个字符串的 [0, j]区间作为研究对象
  dp[i][j]表示字符串 s1 中 [1, i]区间和字符串 s2中 [1, j]区间是否可以匹配

• 状态转移方程：根据s1和s2的最后一个位置，进行讨论

  • p[j]在a - z时，p[j] == s[i] && dp[i - 1][j - 1] == true --- > true
  • p[j] == '.'时，dp[i - 1][j - 1] == true --- > true
  • p[j] == '*'时，再细分
    • p[j - 1] == '.'，对其“翻译”
      • 空串，dp[i][j - 2]
      • 一个点，dp[i - 1][j - 2]
      • 两个点，dp[i - 2][j - 2]
      • ... ... ...；上述有一个true，就是true

      优化：p[j - 1] == '.'

      1. 我们注意到

      • dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i -2][j -2] || ... ...
      • dp[i - 1][j] = dp[i - 1][j -2] || dp[i - 2][j - 2] || dp[i -3][j -2] || ... ...
      • 所以，dp[i][j] = dp[i][j - 2] || dp[i - 1][j]

    • p[j - 1]在a - z时，对其“翻译”
      • 空串，dp[i][j - 2]
      • 匹配一个，然后保留，p[j - 1] == s[i] && dp[i - 1][j]

综上，状态转移方程为：dp[i][j]

• p[j]能匹配时，即s[i] == p[j] || p[j] = '.'，此时看看&& dp[i - 1][j -1]
• dp[i][j -2] || (p[j -1] == ',' || p[j -1] == s[i]) && dp[i -1][j]

• 初始化：引入空串，注意下标映射

  • 初始化整个数组为false
  • dp[0][0]表示两个，初始化为 true
  • 第一列表示 p 为空串，不可能匹配上s 串；
  • 第一行表示s为空串，偶数位置连续为*才为true否则跳出；

• 填表顺序：从上往下，从左往右

• 返回值：dp[m][n]

C++代码

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];
    }
};

交错字符串

题目：交错字符串

思路

• 状态表示：选第一个字符串的 [0, i]区间和第二个字符串的 [0, j]区间作为研究对象
  dp[i][j]表示字符串 s1 中 [1, i]区间内的字符和字符串 s2中 [1, j]区间内的字符是否能够交错组成字符串 s3中 [1, i + j]区间内的字符

• 状态转移方程：根据s1和s2的最后一个位置，进行讨论

  • s3[i + j] = s1[i]，此时s3的最后一个位置和s1的最后一个位置匹配成功，则dp[i][j] = dp[i - 1][j]
  • s3[i + j] = s2[j]，此时s3的最后一个位置和s2的最后一个位置匹配成功，则dp[i][j] = dp[i][j - 1]

• 初始化：

  • dp[0, 0]，因为空串与空串能够构成空串，dp[0][0] = true；
  • 第一行，dp[0][j]，此时s1为空串，判断s2是否符合题意，若s2[j - 1] == s3[j - 1]且 dp[0][j - 1] 为真，则dp[0][j] = true，否则break
  • 第一列，dp[i][0]，此时s2为空串，判断s1是否符合题意，若s1[i - 1] == s3[i - 1]且 dp[i - 1][0] 为真，则dp[i][0] = true，否则break

• 填表顺序：从上往下，从左往右

• 返回值：dp[m][n]，m = s1.size(), n = s2.size()

C++代码

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;
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        s1 = " " + s1, s2 = " " + s2, s3 = " " + 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++)
                dp[i][j] = (s3[i + j] == s1[i] && dp[i - 1][j]) 
                        || (s3[i + j] == s2[j] && dp[i][j - 1]);

        return dp[m][n];
    }
};

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

题目：两个字符串的最小ASCII删除和

思路

给定两个字符串s1和 s2, 返回 使两个字符串相等所需删除字符的 ASCII 值的最小和
<------->
找出s1和s2公共子序列里面，ASCII值的最大和
返回，s1和s2的总ASCII - 2 * 最大和

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

• 状态转移方程：根据s1和s2的最后一个位置，进行讨论

  • 若s1[i] == s2[j]，则说明当前元素是公共子序列的最后一个位置，此时 dp[i][j] = dp[i - 1][j - 1] + s1[i]
  • 若s1[i] != s2[j]
    • 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]
    • 第三种情况已经属于前面两种，综上，dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])

• 初始化：引入空串，注意下标映射

  • 当s1和 s2为空时，没有ASCII值的最大和，所以第一行和第一列为0

• 填表顺序：从左往右，从上往下；

• 返回值：总ASCII - 2 * 最大和（dp[m][n]）

C++代码

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] = dp[i - 1][j - 1] + s1[i - 1];
            }
        }
        int sum = 0;
        for(auto e : s1) sum += e;        
        for(auto e : s2) sum += e;

        return sum - 2 * dp[m][n];
    }
};

最长重复子数组

题目：最长重复子数组

思路

• 状态表示：dp[i][j]表示以第一个数组的第 i位置为结尾以及第二个数组的第j 位置为结尾时，两个数组的最长重复子数组的长度和

• 状态转移方程：

  • 若nums1[i] == nums2[j]，则说明当前元素 加上 以i - 1, j - 1 为结尾的最长重复子数组的长，此时 dp[i][j] = dp[i - 1][j - 1] + 1

• 初始化：添加了一行和一列，注意下标映射

  • 第一行表示第一个数组为空，此时没有重复子数组，初始化为 0
  • 第一列表示第二个数组为空，此时没有重复子数组，初始化为 0

• 填表顺序：从左往右，从上往下；

• 返回值：dp 表中的最大值

C++代码

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