难度：★★★☆☆
类型：数组
方法：动态规划

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

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

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

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

示例 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

提示：

1 <= A.length <= 500
1 <= B.length <= 500
1 <= A[i], B[i] <= 2000

解答

这是穿了马甲的最长公共非连续子序列问题，我们逐层剖析。

两个序列的公共最长连续子序列

序列可能是数组或者字符串。

题目请参考求两个序列的最长公共子序列

对于序列A和B，我们需要找到这两个序列的最长公共子序列（连续）。

【数组定义】
设序列A和B长度分别为la和lb，定义二维数组dp，维度为(la+1)*(lb+1)，dp[ia][ib]表示序列A[:ia]和序列A[:ib]的最长公共子序列（连续）。这里维度+1的原因是，A的连续序列的长度是从0到la，一共la个，B序列同理。

【初始状态】
定义dp数组中所有值为零。

【递推公式】
在满足A[ia]==B[ib]时，说明A[:ia+1]和B[:ib+1]的末尾字符实现匹配，dp[ia+1][ib+1]的结果取决于dp[ia][ib]，也就是dp[ia+1][ib+1] = dp[ia][ib] + 1。

【返回值】
返回dp二维数组中的最大值即可。

class Solution:
    def findLength(self, A, B):
        la, lb = len(A), len(B)
        dp = [[0 for _ in range(lb + 1)] for _ in range(la + 1)]
        for ia in range(la):
            for ib in range(lb):
                if A[ia] == B[ib]:
                    dp[ia+1][ib+1] = dp[ia][ib] + 1
        return max(map(max, dp))

如果公共子序列没有连续的限制呢？

这时候，其他的都不用变，主要考虑递推公式中，A[ia]!=B[ib]时的情况，这时，dp[ia+1][ib+1]的来源变成了两个，dp[ia][ib+1], dp[ia+1][ib]，取其中最大值。dp[ia+1][ib+1] = max(dp[ia][ib+1], dp[ia+1][ib])。

题目见不要求连续

class Solution:
    def longestCommonSubsequence(self, A: str, B: str) -> int:
        la, lb = len(A), len(B)
        dp = [[0 for _ in range(lb + 1)] for _ in range(la + 1)]
        for ia in range(la):
            for ib in range(lb):
                if A[ia] == B[ib]:
                    dp[ia+1][ib+1] = dp[ia][ib] + 1
                else:
                    dp[ia+1][ib+1] = max(dp[ia][ib+1], dp[ia+1][ib])
        return max(map(max, dp))

穿了马甲的问题

这道题的实质还是求两个序列的公共最长非连续子序列问题。因为这个序列的连线一定是不相交的，且连线数量一定是最长的。

class Solution:
    def maxUncrossedLines(self, A: str, B: str) -> int:
        la, lb = len(A), len(B)
        dp = [[0 for _ in range(lb + 1)] for _ in range(la + 1)]
        for ia in range(la):
            for ib in range(lb):
                if A[ia] == B[ib]:
                    dp[ia+1][ib+1] = dp[ia][ib] + 1
                else:
                    dp[ia+1][ib+1] = max(dp[ia][ib+1], dp[ia+1][ib])
        return max(map(max, dp))

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析