LC 1035. Uncrossed Lines

https://leetcode.com/problems/uncrossed-lines/

这题目想到动态规划不是很难，而且可以使用滚动窗口优化空间。主要是这题目的数据集优化特别有意思，我们只需要关系A,B两个集合的交集即可，因为对于那些不在交集里面的点，完全可以直接抛弃，而不对结果有任何一下影响。提交时间可以从252ms->96ms. 其实这些优化点不难想到，主要还是看是否留心。

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        # note(yan): discusson里面提到的优化点，只保留AB两个的交集
        commons = set(A) & set(B)
        A = [x for x in A if x in commons]
        B = [x for x in B if x in commons]

        n = len(A)
        m = len(B)
        dp = [[0] * (m + 1), [0] * (m + 1)]
        now = 0

        for i in range(n):
            for j in range(m):
                dp[1 - now][j + 1] = max(dp[now][j + 1], dp[1 - now][j], dp[now][j] + (1 if A[i] == B[j] else 0))
            now = 1 - now

        ans = dp[now][m]
        return ans