双序列型动态规划——最长公共子序列

雨点打透心脏的1/2处 2022-10-27 12:07 168阅读 0赞

#  #

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。  
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

输入：text1 = "abcde", text2 = "ace" 
    输出：3  
    解释：最长公共子序列是 "ace"，它的长度为 3。

### 1、题目分析 ###

公共子串一定是对应的字符按顺序都相等

找到最长的对应对子，且对子连线不能相交

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]

### 2、确定状态 ###

设A长度是m, B长度是n

最后一步：观察A\[m-1\]和B\[n-1\]这两个字符是否作为一个对子在最优策略中

如果A\[m-1\]在，则需要求A\[0…m-2\]和B\[0…n-1\]的最长公共子串，

如果B\[n-1\]在，则需要求A\[0…m-1\]和B\[0…n-2\]的最长公共子串，

如果两个都在，则需要求A\[0…m-2\]和B\[0…n-2\]的最长公共子串。

所以我们可以假设状态f\[i\]\[j\]为A前i个字符A\[0…i-1\]和B前j个字符\[0…j-1\]的最长公共子串的长度。

### 3、转移方程 ###

假设状态f\[i\]\[j\]为A前i个字符A\[0…i-1\]和B前j个字符\[0…j-1\]的最长公共子串的长度

![在这里插入图片描述][20210203221627947.png]

### 4、初始条件和边界情况 ###

初始条件：空串和任何串的最长公共子串长度是0

– f\[0\]\[j\] = 0, j=0…n

– f\[i\]\[0\] = 0, i=0…m

### 5、计算顺序 ###

逐行计算。答案f\[m\]\[n\]

时间复杂度：O(MN)；空间复杂度：O(MN)

### 6、代码实现 ###

class Solution:
        def longestCommonSubsequence(self, text1: str, text2: str) -> int:
            m=len(text2)+1
            dp=[[0]*m for i in range(n)]
            pt=[[0]*m for i in range(n)]
            for i in range(n):
                for j in range(m):
                    if i==0:
                        dp[i][j]=0
                        continue
                    if j==0:
                        dp[i][j]=0
                        continue
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])
                    if text1[i-1]==text2[j-1]:
                        dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1)
            return dp[n-1][m-1]

#  #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]: /images/20221024/550a305254af4056ab91cfc943252a8b.png
[20210203221627947.png]: /images/20221024/42a9aa2245344078a7d07e75c3ee8f1f.png