【动态规划】两个数组 / 字符串的dp问题（子序列、子数组问题、匹配问题、字符串问题）

思路

1. 定义状态：

   • 用一个二维数组 dp 来存储状态，其中 dp[i][j] 代表字符串 text1 的前 i 个字符和字符串 text2 的前 j 个字符的最长公共子序列的长度。

2. 状态转移：

   • 如果 text1[i-1] 等于 text2[j-1]，则 dp[i][j] 取 dp[i-1][j-1] 的值加 1。
   • 如果不等，dp[i][j] 取 dp[i-1][j] 和 dp[i][j-1] 中的较大值。

3. 初始化：

   • dp 数组初始化为 0。

4. 结果：

   • 最终的结果是 dp[m][n]，即两个字符串的最长公共子序列的长度。

代码

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m = text1.size(), n = text2.size();// 创建+初始化dp数组// dp[i][j]：在s1串 的{0, 1}范围 和 s2串的{0, j}范围的最长公共子序列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){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];}
};

思路

这道题实际上就是上一题的变体，也就是求最长公共子序列。

代码

class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {// 即[1143.最长公共子序列](https://leetcode.cn/problems/longest-common-subsequence/description/)int m = nums1.size(), n = nums2.size();// 创建 + 初始化dp数组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){if(nums1[i - 1] == nums2[j - 1]) // 下标映射dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = max(dp[i][j-1], dp[i-1][j]);}return dp[m][n];}
};

思路

1. 状态定义：dp[i][j] 表示字符串 s 的前 j 个字符中，t 的前 i 个字符作为子序列的数量。

2. 初始化：dp[0][j] = 1，表示 t 是空字符串时，任何 s 的前 j 个字符中都有 1 种不同的子序列（即空子序列）。

3. 状态转移：

   • dp[i][j] += dp[i][j-1]：在当前字符 s[j-1] 不包含在子序列中的情况下的数量。
   • 如果 t[i-1] == s[j-1]，则 dp[i][j] += dp[i-1][j-1]，表示包含当前字符 s[j-1] 时的数量。

4. 结果：dp[m][n]，表示 s 中包含 t 的所有不同子序列的数量。

• 时间复杂度 O(m * n)
• 空间复杂度 O(m * n)。

代码

class Solution {
public:int numDistinct(string s, string t) {int m = t.size(), n = s.size();// 创建+初始化 dp数组vector<vector<int>> dp(m+1, vector<int>(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];}
};

思路

1. 状态定义：

   • dp[i][j] 表示字符串 s 的前 i 个字符是否可以被模式 p 的前 j 个字符匹配。

2. 初始化：

   • dp[0][0] = true：空字符串和空模式是匹配的。
   • 对于模式中的 *，dp[0][j] 需要设置为 true，因为 * 可以匹配零个字符。初始化时，从模式的开头开始，连续的 * 会让 dp[0][j] 设为 true。

3. 状态转移：

   • 当模式字符 p[j] 是 * 时，dp[i][j] 可以由以下两种情况获得：
     • dp[i-1][j]：表示模式 p 的 * 匹配了 s 的当前字符，并且剩余的 s 部分可以继续匹配模式。
     • dp[i][j-1]：表示模式 p 的 * 匹配了零个字符，即模式的 * 前面的部分与 s 的当前部分匹配。
   • 当模式字符 p[j] 不是 * 时，dp[i][j] 的值取决于当前模式字符是否等于 s 的当前字符，或者模式字符是否为 ?。如果是，则 dp[i][j] 可以由 dp[i-1][j-1] 获得。

4. 结果：

   • 最终的结果是 dp[m][n]，表示整个字符串 s 是否可以被模式 p 匹配。

• 时间复杂度：O(m * n)，因为我们需要填充 m * n 的 dp 表。
• 空间复杂度：O(m * n)，使用了一个 m+1 行、n+1 列的二维数组来存储中间结果。

代码

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)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];}   else {dp[i][j] = (p[j] == '?' || p[j] == s[i]) && dp[i-1][j-1];}}return dp[m][n];}
};

思路

1. 初始化：

   • 在字符串 s 和模式 p 前面各加一个空格（即使 s 和 p 从索引 1 开始），这样可以简化下标操作，使 s[i] 和 p[j] 对应的下标与 dp 表一致。
   • 创建一个二维布尔数组 dp，其中 dp[i][j] 表示字符串 s 的前 i 个字符是否与模式 p 的前 j 个字符匹配。

2. 处理模式的初始化：

   • 初始化 dp[0][j]，这表示空字符串与模式 p 的前 j 个字符的匹配。因为 * 可以匹配零个或多个字符，所以当模式的第 j 个字符是 * 时，我们需要检查 dp[0][j-2]（即模式中 * 前面的字符可能不出现的情况）。

3. 填表：

   • 对于每个字符 s[i] 和 p[j]，检查模式 p 当前字符是 * 还是普通字符。
   • 如果是 *，有两个匹配条件：
     • dp[i][j-2]：表示 * 匹配零个字符。
     • (p[j-1] == '.' || p[j-1] == s[i]) && dp[i-1][j]：表示 * 匹配一个或多个字符。
   • 如果是普通字符，检查 p[j] 是否与 s[i] 匹配，或者 p[j] 是否为 .，然后根据 dp[i-1][j-1] 更新 dp[i][j]。

4. 返回结果：

   • 最终的匹配结果保存在 dp[m][n] 中。

• 时间复杂度：O(m * n)。由于我们使用了一个 m+1 行和 n+1 列的二维 DP 表，且每个元素的计算都需要常量时间，所以总体时间复杂度是 O(m * n)。

• 空间复杂度：O(m * n)。我们使用了一个 m+1 行和 n+1 列的二维 DP 表来存储中间结果。因此，空间复杂度为 O(m * n)。

代码

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表dp[0][0] = true;for(int j = 2; j <= n; j+=2)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][j-2] || (p[j-1] == '.' || p[j-1] == s[i]) && dp[i-1][j];elsedp[i][j] = dp[i-1][j-1] && (p[j] == s[i] || p[j] == '.');}return dp[m][n];}
};

思路

1. 初始化：

   • 创建一个二维 DP 数组 dp[i][j]，其中 dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符是否能交错组成 s3 的前 i+j 个字符。
   • dp[0][0] 初始化为 true，表示空字符串可以交错合成空字符串。
   • 对 dp[0][j] 和 dp[i][0] 进行初始化，分别处理当 s1 或 s2 为空的情况。

2. 填表：

   • 遍历 DP 表，更新每个 dp[i][j]，根据 s1[i-1] 和 s2[j-1] 是否等于 s3[i+j-1] 来决定是否更新 dp[i][j]。

时空复杂度：

• 时间复杂度：O(m * n)，其中 m 是 s1 的长度，n 是 s2 的长度。填充 DP 表需要遍历所有 m * n 的位置。
• 空间复杂度：O(m * n)，需要一个大小为 m * n 的 DP 表。

代码

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;// 创建dp数组// dp[i][j]: s1{1, i}区间 与 s2[1, j]区间是否能匹配s3{1, i+j}区间vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));// 初始化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] = (s2[j] == s3[i+j] && dp[i][j-1])||(s1[i] == s3[i+j] && dp[i-1][j]);}return dp[m][n];}
};

思路

1. 定义状态：

   • dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符的公共子序列的最大ASCII值之和。

2. 初始化和状态转移：

   • 初始化 dp[i][0] 和 dp[0][j] 为0，因为一个字符串为空时，公共子序列的ASCII和为0。
   • 对于每对 (i, j)，比较 s1[i-1] 和 s2[j-1]：
     • 如果它们相同，则 dp[i][j] 为 dp[i-1][j-1] + s1[i-1]。
     • 否则，dp[i][j] 为 max(dp[i-1][j], dp[i][j-1])。

3. 计算结果：

   • 计算所有字符的ASCII和，并从中减去两次 dp[m][n]，因为每个字符被计算了两次。

时空复杂度：

• 时间复杂度：O(m * n)，填充 DP 表需要遍历所有 m * n 的位置。
• 空间复杂度：O(m * n)，需要一个大小为 m * n 的 DP 表。

代码

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));// 正难则反：求公共子序列的最大ASCII值for(int i = 1; i <= m; ++i)for(int j = 1; j <= n; ++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]);}int sum = 0;for(char ch1 : s1) sum += ch1;for(char ch2 : s2) sum += ch2;return sum - dp[m][n] - dp[m][n]; // 两个字符串 需要减两次}
};

思路

1. 状态定义：

   • dp[i][j] 表示 nums1 中前 i 个元素和 nums2 中前 j 个元素的最长公共子数组的长度。

2. 初始化：

   • dp 数组初始化为 0。默认情况下，如果 i 或 j 为 0，公共子数组的长度为 0。

3. 状态转移：

   • 如果 nums1[i - 1] 和 nums2[j - 1] 相等，则 dp[i][j] = dp[i-1][j-1] + 1。如果不相等，dp[i][j] 保持为 0。
   • 更新 ret 为 dp[i][j] 和当前 ret 的最大值，得到最大长度的公共子数组。

4. 返回值：

   • 返回 ret，即最长公共子数组的长度。

时间复杂度：O(m * n)，需要遍历所有 m * n 的位置。

空间复杂度：O(m * n)，需要一个大小为 m * n 的 DP 表。

代码

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size(), n = nums2.size();// 创建dp数组 + 初始化// nums1以i为结尾的子数组 与 num2以j为结尾的子数组 最长重复子数组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;}
};