对于两个字符串求子序列的问题，都是用两个指针i和j分别在两个字符串上移动，大概率是使用动态规划

最长公共子序列（力扣1143）

题目

1
2
3
4
5
6
>给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

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

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

示例 1:

1
2
3
>输入：text1 = "abcde", text2 = "ace" 
>输出：3  
>解释：最长公共子序列是 "ace"，它的长度为 3。示例 2:
1
2
3
>输入：text1 = "abc", text2 = "abc"
>输出：3
>解释：最长公共子序列是 "abc"，它的长度为 3。示例 3:
1
2
3
>输入：text1 = "abc", text2 = "def"
>输出：0
>解释：两个字符串没有公共子序列，返回 0。

分析

假设text1={s1,s2,s3,...,si},text2={t1,t2,t3,...,tj}text1 = \{s_1,s_2,s_3,...,s_i\}, text2 = \{t_1,t_2,t_3,...,t_j\}

(1) 如果text1text1的最后一位等于text2text2的最后一位，则最大子序列就是{s1,s2,s3,...,si−1}\{s_1,s_2,s_3,...,s_{i-1}\}和{t1,t2,t3,...,tj−1}\{t_1,t_2,t_3,...,t_{j-1}\}的最大子序列+1

(2) 如果text1text1的最后一位不等于text2text2的最后一位，那么最大子序列就是

{s1,s2,s3,...,si}\{s_1,s_2,s_3,...,s_i\}和 {t1,t2,t3,...,tj−1}\{t_1,t_2,t_3,...,t_{j-1}\} 的最大重复子序列与 {s1,s2,s3,...,si−1}\{s_1,s_2,s_3,...,s_{i-1}\}和 {t1,t2,t3,...,tj}\{t_1,t_2,t_3,...,t_{j}\} 的最大重复子序列的最大值

(3)base case

我们假设将两个字符串前添加一个不同的字符，这样可以将dp数组的第一行和第一列都初始化为空。dp数组从dp[1][1]开始填充。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        ## dp = [[0]*(n+1)]*(m+1)
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        print(len(dp))
        ans = 0
        for i in range(1,m+1):
            for j in range(1,n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                    ans = max(ans, dp[i][j])
                else:
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])
        print(dp)
        return ans
Solution = Solution()
Solution.longestCommonSubsequence("abcba","abcbcba")

这里注意第4行的这种方式生成二维数组，因为是使用了引用，当改变第1列时，第0列的也会发生改变，导致结果错误。

如下所示：

1
2
3
4
dp = [[0]*(n+1)]*(m+1)
dp[1][1] = 1
print(dp)
# [[0, 1, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0]]

可以看到，所有的列都发生了改变。

最长重复子数组（力扣718）

题目

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

1
2
3
4
5
6
7
8
>示例：

>输入：
>A: [1,2,3,2,1]
>B: [3,2,1,4,7]
>输出：3
>解释：
>长度最长的公共子数组是 [3, 2, 1] 。

分析

状态转移方程和最长重复子串一致，但需要注意的是：子数组必须是连续的，而子串不需要连续，所以需要做出改变。将上题解法的else去掉，即当不连续时直接设为0，我们直接写出动态规划的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        ## dp = [[0]*(n+1)]*(m+1)
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        print(len(dp))
        ans = 0
        for i in range(1,m+1):
            for j in range(1,n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                    ans = max(ans, dp[i][j])
                #else:
                #    dp[i][j] = max(dp[i][j-1], dp[i-1][j])
        return ans
Solution = Solution()
Solution.longestCommonSubsequence("abcba","abcbcba")

不相交的线(力扣1035)

题目

我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。

现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。

以这种方法绘制线条，并返回我们可以绘制的最大连线数。

img

示例 1：

输入：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

分析

其实就是最大重复子序列

参考