【动态规划】两个数组的dp问题（一）

📝前言说明：

• 本专栏主要记录本人的动态规划算法学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

你可以点击下方链接，进行不同专题的动态规划的学习

点击链接 开始学习 斐波那契数列模型 路径问题 简单多状态（一） 简单多状态（二） 子数组系列（一） 子数组系列（二） 子序列问题（一） 子序列问题（二） 回文串（一） 回文串（二） 两个数组dp问题（一） 两个数组的dp问题（二） 01背包问题 完全背包 二维的背包问题 其他

题单汇总链接：点击 → 题单汇总

题目

• 1143. 最长公共子序列（重点）
• • 优质解
• 1035. 不相交的线
• • 个人解
• 115. 不同的子序列
• • 优质解
• 44. 通配符匹配
• • 优质解

---

1143. 最长公共子序列（重点）

题目链接：https://leetcode.cn/problems/longest-common-subsequence/

---

优质解

思路：
状态表示

• 经验：选取 s1 的[0, i]区间以及 s2 [0, j]区间作为研究对象
• 题目要求：根据题目要求结合经验写出状态表示
• 状态表示：dp[i][j]： s1 的[0, i]区间以及 s2 的[0, j]区间内所有子序列中，最长公共子序列的长度

状态转移方程

• 经验：根据最后一个位置的状况，分情况讨论
• 情况1 s1[i] == s2[j]：则公共子序列必以s[i]为结尾，此时可以转换成：s1[0, i - 1]和s2[0, j - 1]的最长公共子序列 + 字符 s[i]。
  • 即：dp[i][j] = dp[i - 1][j - 1] + 1
• 情况2 s1[i] != s2[j]，则最长公共子序列不可能同时包含s[i]和 s[j]
  • 去 s1[0, i - 1] 和s2 [0, j] 找
    • 即：dp[i - 1][j]
  • 去 s1[0, i] 和 s2 [0, j - 1] 找
    • 即：dp[i][j - 1]
  • 去 s1 [0, i - 1] 和 s2 [0, j - 1]找（但是注意：第一种情况里面已经包含了这一个，所以我们可以不用管这个情况【因为本题是求max】）
    • dp[i - 1][j - 1]

初始化

• 空串也属于公共子序列（引入空串，方便初始化）
• 多加上面一行和左边一列（此时 i 和 j从 1开始，不会越界）
  • 且全为 0（因为是求最大值，所以填 0能保证后续结果不受影响）
  • 映射关系：原来的dp[i][j]映射到 dp[i + 1][j + 1]（字符串0位置就要映射到dp[1]了）
    • 解决方法：我们可以在字符串前加一个字符，让字符串的下标再次和dp表的下标对应

填表顺序

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

返回值

• dp[m][n]，m为s1长度，n为s2长度

代码：

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

时间复杂度：$O(m\ast n)$
空间复杂度：$O(m\ast n)$

---

1035. 不相交的线

题目链接：https://leetcode.cn/problems/uncrossed-lines/description/

个人解

思路：

• 就是子序列（因为不交叉）
  用时：10:00

屎山代码：

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

时间复杂度：$O(m\ast n)$
空间复杂度：$O(m\ast n)$

---

115. 不同的子序列

题目链接：https://leetcode.cn/problems/distinct-subsequences/description/

---

优质解

思路：
状态表示

• dp[i][j]: 子串 t[0, i] 在 s 的 [0, j] 区间中的所有子序列中出现的个数

状态转移方程：子串t[0, i]包不包含s[j]

• 包含：则一定是t[i] == s[j]：dp[i][j] = dp[i - 1][j - 1]
• 不包含：则dp[i][j] == dp[i][j - 1]
• 所以：dp[i][j] = dp[i][j - 1] + dp[i][j] = dp[i - 1][j - 1](if t[i] == s[j])

初始化

• 引入空串，下标映射，填表的空串的值（为了不影响结果）
• 第一行全1：s是空串时，s总有一个t为空串的子序列
• 第一列：除[0][0]，全0

代码：

class Solution {public: int numDistinct(string s, string t) { int m = t.size(), n =s.size(); vector<vector<unsigned>> dp(m + 1, vector<unsigned>(n + 1, 0)); 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++) { if(t[i - 1] == s[j - 1]) dp[i][j] += dp[i - 1][j - 1]; dp[i][j] += dp[i][j - 1]; } } return dp[m][n]; }};

时间复杂度：$O(m\ast n)$
空间复杂度：$O(m\ast n)$

---

44. 通配符匹配

题目链接：https://leetcode.cn/problems/wildcard-matching/description/

优质解

思路：

• dp[i][j]: 代表模式串[0, i] 能否匹配 字符串[0, j]
• 按模式串的第 i 个字符串来分类
  • 普通字符: dp[i][j] = dp[i - 1][j - 1] && s[j] == p[i]
  • ‘?’ 字符: dp[i][j] = dp[i - 1][j - 1]
  • ‘*’ 字符: dp[i][j] = dp[i - 1][k](0 <= k <= j) 只要有一个位置为 true 就返回ture
• 问题在于第三个’*’ 字符，如果拿k遍历一遍，时间复杂度太高。
  • 于是，由数学推导：dp[i][j] == dp[i - 1][j] ||dp[i - 1][j - 1] || dp[i - 1][j - 2] || ... dp[i - 1][0]
  • 我们看除去第一项的后面的项的结果，刚好是 dp[i][j - 1]的展开
  • 所以化简得到：dp[i][j] = dp[i - 1][j] || dp[i][j - 1]
• 初始化：需要注意的是：空串可以匹配空串，\'*\'也可以匹配空串（模式串可以前导多个\'*\'，此时将它们都匹配上空串）

代码：

class Solution {public: bool isMatch(string s, string p) { int m = p.size(), n = s.size(); vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false)); // 添加空串 dp[0][0] = true; for(int i = 1; i <= m; i++) { if(p[i - 1] == \'*\') dp[i][0] = true; else break; // 当模式串的第一个位置不是 `*`开始匹配 } for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { if(p[i - 1] == \'?\')  dp[i][j] = dp[i - 1][j - 1]; else if(p[i - 1] >= \'a\' && p[i - 1] <= \'z\')  dp[i][j] = dp[i - 1][j - 1] && s[j - 1] == p[i - 1]; else  dp[i][j] = dp[i - 1][j] || dp[i][j - 1]; } } return dp[m][n]; }};

时间复杂度：$O(m\ast n)$
空间复杂度：$O(m\ast n)$

---

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！