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

最长公共子序列

题目：最长公共子序列

思路

选取s1的[0, i]区间以及s2的[0， j]区间作为研究对象

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

• 状态转移方程：

  • s1[i] == s2[j]时，即最长公共子序列以s1[i]结尾，所以有dp[i][j] = dp[i - 1][j - 1] + 1
  • s1[i] != s2[j]时，最长公共子序列一定不以s1[i]结尾，所以
    1. 去s1的[0, i - 1]区间以及s2的[0， j]区间寻找答案，即dp[i][j] = dp[i - 1][j]
    2. 去s1的[0, i]区间以及s2的[0，j - 1 ]区间寻找答案，即dp[i][j] = dp[i][j - 1]
    3. 去s1的[0, i - 1]区间以及s2的[0， j - 1]区间寻找答案，即dp[i][j] = dp[i - 1][j - 1]
    • 综上，1和2以及包括3，所以dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])

• 初始化：引入空串，帮助我们初始化
  在s1, s2前添加一个空字符，也就是说s1[0]和s2[0]的位置的值是空串;
  dp表的大小为 (m+1) x (n+1)，其中 m 和n 是s1和s2的长度。初始化时，将第一行和第一列的值都设置为0
  注意下标的映射

• 填表顺序：每次i和j都需要用到i - 1和j - 1，所以从上往下填，从左往右填

• 返回值：dp[m][n]，其中 m 和n 是s1和s2的长度

C++代码

class Solution 
{
public:int longestCommonSubsequence(string text1, string text2) {int m = text1.size(), n = text2.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++)if(text1[i - 1] == text2[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];}   
};

不相交的线

题目：不相交的线

思路

阅读本题后发现和上题解法基本相同

C++代码

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));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;elsedp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);return dp[m][n];}
};

不同的子序列

题目：不同的子序列

思路

选取t的[0, i]区间以及s的[0， j]区间作为研究对象

• 状态表示：dp[i][j]表示，s的[0, j]区间内所有的子序列中，有多少个t的[0， i]区间内的子串
• 状态转移方程：根据s的子序列包不包含s[j]来划分
  • 包含s[j]时，t[i] == s[j]，此时dp[i][j] = dp[i - 1][j - 1]
  • 不包含s[j]时，此时dp[i][j] = dp[i][j - 1]
• 初始化：引入空串，注意下标的映射，
  • 当 t为空时，s中至少有一个空串是其子串，所以第一行为1
  • 当 s为空时，t只有是空串时，符合题意，第一列除了第一个都是0
• 填表顺序：i和j填写都需要用到i - 1和j - 1，所以从上往下填，从左往右填
• 返回值：dp[m][n]，其中 m 和n 是t和s的长度

C++代码

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;for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++){dp[i][j] += dp[i][j - 1];if(t[i - 1] == s[j - 1]) dp[i][j] += dp[i - 1][j - 1];}return dp[m][n];}
};  

通配符匹配

题目：通配符匹配

思路

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

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

• 状态转移方程：根据根据最后一个位置的元素，来讨论

  • p[j]是普通字符，s[i] == p[j] && dp[i - 1][j - 1] == true ->true
  • p[j] == '?'，dp[i - 1][j - 1] == true -> true
  • p[j] == '*'
    • 匹配空串，dp[i][j - 1]
    • 匹配一个字符s[i]， dp[i - 1][j - 1]
    • 匹配两个字符s[i]、s[i - 1]，dp[i - 2][j - 1]
    • ... ... ... ...

    优化p[j] == '*'

    • 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 - 1] || dp[i - 1][j]
    • 匹配空串，dp[i][j - 1]
    • 匹配一个，但不舍去*，dp[i - 1][j]
    • 所以，dp[i][j] = dp[i][j - 1] || dp[i - 1][j]

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

  • 初始化整个数组为false
  • dp[0][0]表示两个空串是否匹配，初始化为true
  • 第一行表示s 为空串，p 串与空串只有一种匹配可能，即 p 串表示为 "***"，此时也相当于空串匹配上空串，将所有前导为 "*" 的 p子串与空串的 dp 值设为true

• 填表顺序：i和j填写都需要用到i - 1和j - 1，所以从上往下填，从左往右填

• 返回值：dp[m][n]，其中 m 和n 是s和p的长度

C++代码

class Solution 
{
public:bool isMatch(string s, string p) {int m = s.size(), n = p.size();vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));s = " " + s;p = " " + p;dp[0][0] = true;for(int j = 1; j <= n; j++)if(p[j] == '*') dp[0][j] = 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 - 1][j] || dp[i][j - 1];elsedp[i][j] = (p[j] == '?' || s[i] == p[j]) && dp[i -1][j - 1];}return dp[m][n];}
};