你的衣服我扒了 * 《最長公共子序列》 · 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)