你的衣服我扒了 * 《最长公共子序列》 · ttttt

# 你的衣服我扒了 \* 《最长公共子序列》 # 你的衣服我扒了 - 《最长公共子序列》之前出了一篇[穿上衣服我就不认识你了？来聊聊最长上升子序列](https://lucifer.ren/blog/2020/06/20/LIS/)，收到了大家的一致好评。今天给大家带来的依然是换皮题 - 最长公共子序列系列。最长公共子序列是一个很经典的算法题。有的会直接让你求最长上升子序列，有的则会换个说法，但最终考察的还是最长公共子序列。那么问题来了，它穿上衣服你还看得出来是么？如果你完全看不出来了，说明抽象思维还不到火候。经常看我的题解的同学应该会知道，我经常强调`抽象思维`。没有抽象思维，所有的题目对你来说都是新题。你无法将之前做题的经验迁移到这道题，那你做的题意义何在？虽然抽象思维很难练成，但是幸好算法套路是有限的，经常考察的题型更是有限的。从这些入手，或许可以让你轻松一些。本文就从一个经典到不行的题型《最长公共子序列》，来帮你进一步理解`抽象思维`。 > 注意。本文是帮助你识别套路，从横向上理清解题的思维框架，并没有采用最优解，所有的题目给的解法可能不是最优的，但是都可以通过所有的测试用例。如果你想看最优解，可以直接去讨论区看。或者期待我的`深入剖析系列`。 ## 718. 最长重复子数组 ### 题目地址 <https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/> ### 题目描述 ``` <pre class="calibre18">``` 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。示例 1: 输入: A: [1,2,3,2,1] B: [3,2,1,4,7] 输出: 3 解释: 长度最长的公共子数组是 [3, 2, 1]。说明: 1 <= len(A), len(B) <= 1000 0 <= A[i], B[i] < 100 ``` ``` ### 前置知识 - 哈希表 - 数组 - 二分查找 - 动态规划 ### 思路这就是最经典的最长公共子序列问题。一般这种求解**两个数组或者字符串求最大或者最小**的题目都可以考虑动态规划，并且通常都定义 dp\[i\]\[j\] 为 `以 A[i], B[j] 结尾的 xxx`。这道题就是：`以 A[i], B[j] 结尾的两个数组中公共的、长度最长的子数组的长度`。 > 关于状态转移方程的选择可以参考： [穿上衣服我就不认识你了？来聊聊最长上升子序列](https://lucifer.ren/blog/2020/06/20/LIS/) 算法很简单： - 双层循环找出所有的 i, j 组合，时间复杂度 O(m∗n)O(m \* n)O(m∗n)，其中 m 和 n 分别为 A 和 B 的长度。 - 如果 A\[i\] == B\[j\]，dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\] + 1 - 否则，dp\[i\]\[j\] = 0 - 循环过程记录最大值即可。 **记住这个状态转移方程，后面我们还会频繁用到。** ### 关键点解析 - dp 建模套路 ### 代码代码支持：Python Python Code: ``` <pre class="calibre18">``` class Solution: def findLength(self, A, B): m, n = len(A), len(B) ans = 0 dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if A[i - 1] == B[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 ans = max(ans, dp[i][j]) return ans ``` ``` **复杂度分析** - 时间复杂度：O(m∗n)O(m \* n)O(m∗n)，其中 m 和 n 分别为 A 和 B 的长度。 - 空间复杂度：O(m∗n)O(m \* n)O(m∗n)，其中 m 和 n 分别为 A 和 B 的长度。 > 二分查找也是可以的，不过并不容易想到，大家可以试试。 ## 1143.最长公共子序列 ### 题目地址 <https://leetcode-cn.com/problems/longest-common-subsequence> ### 题目描述给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。若这两个字符串没有公共子序列，则返回 0。示例 1: 输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace"，它的长度为 3。示例 2: 输入：text1 = "abc", text2 = "abc" 输出：3 解释：最长公共子序列是 "abc"，它的长度为 3。示例 3: 输入：text1 = "abc", text2 = "def" 输出：0 解释：两个字符串没有公共子序列，返回 0。提示: 1 <= text1.length <= 1000 1 <= text2.length <= 1000 输入的字符串只含有小写英文字符。 ### 前置知识 - 数组 - 动态规划 ### 思路和上面的题目类似，只不过数组变成了字符串（这个无所谓），子数组（连续）变成了子序列（非连续）。算法只需要一点小的微调： `如果 A[i] != B[j]，那么 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])` ### 关键点解析 - dp 建模套路 ### 代码 > 你看代码多像代码支持：Python Python Code: ``` <pre class="calibre18">``` class Solution: def longestCommonSubsequence(self, A: str, B: str) -> int: m, n = len(A), len(B) ans = 0 dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if A[i - 1] == B[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 ans = max(ans, dp[i][j]) else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return ans ``` ``` **复杂度分析** - 时间复杂度：O(m∗n)O(m \* n)O(m∗n)，其中 m 和 n 分别为 A 和 B 的长度。 - 空间复杂度：O(m∗n)O(m \* n)O(m∗n)，其中 m 和 n 分别为 A 和 B 的长度。 ## 1035. 不相交的线 ### 题目地址 <https://leetcode-cn.com/problems/uncrossed-lines/description/> ### 题目描述我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。现在，我们可以绘制一些连接两个数字 A\[i\] 和 B\[j\] 的直线，只要 A\[i\] == B\[j\]，且我们绘制的直线不与任何其他连线（非水平线）相交。以这种方法绘制线条，并返回我们可以绘制的最大连线数。示例 1： ![](https://img.kancloud.cn/cf/38/cf38b71df51cb760edfdfde3dddc2590_1509x1080.jpg) 输入：A = \[1,4,2\], B = \[1,2,4\] 输出：2 解释：我们可以画出两条不交叉的线，如上图所示。我们无法画出第三条不相交的直线，因为从 A\[1\]=4 到 B\[2\]=4 的直线将与从 A\[2\]=2 到 B\[1\]=2 的直线相交。示例 2：输入：A = \[2,5,1,2,5\], B = \[10,5,2,1,5,2\] 输出：3 示例 3：输入：A = \[1,3,7,1,7,5\], B = \[1,9,2,5,1\] 输出：2 提示： 1 <= A.length <= 500 1 <= B.length <= 500 1 <= A\[i\], B\[i\] <= 2000 ### 前置知识 - 数组 - 动态规划 ### 思路从图中可以看出，如果想要不相交，则必然相对位置要一致，换句话说就是：**公共子序列**。因此和上面的 `1143.最长公共子序列` 一样，属于换皮题，代码也是一模一样。 ### 关键点解析 - dp 建模套路 ### 代码 > 你看代码多像代码支持：Python Python Code: ``` <pre class="calibre18">``` class Solution: def longestCommonSubsequence(self, A: str, B: str) -> int: m, n = len(A), len(B) ans = 0 dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if A[i - 1] == B[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 ans = max(ans, dp[i][j]) else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return ans ``` ``` **复杂度分析** - 时间复杂度：O(m∗n)O(m \* n)O(m∗n)，其中 m 和 n 分别为 A 和 B 的长度。 - 空间复杂度：O(m∗n)O(m \* n)O(m∗n)，其中 m 和 n 分别为 A 和 B 的长度。 ## 总结第一道是“子串”题型，第二和第三则是“子序列”。不管是“子串”还是“子序列”，状态定义都是一样的，不同的只是一点小细节。 **只有熟练掌握基础的数据结构与算法，才能对复杂问题迎刃有余。** 基础算法，把它彻底搞懂，再去面对出题人的各种换皮就不怕了。相反，如果你不去思考题目背后的逻辑，就会刷地很痛苦。题目稍微一变化你就不会了，这也是为什么很多人说**刷了很多题，但是碰到新的题目还是不会做**的原因之一。关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。更多题解可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。目前已经 37K star 啦。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)