1035.不相交的线

链接：1035.不相交的线
难度：Medium
标签：数组、动态规划
简介：以这种方法绘制线条，并返回可以绘制的最大连线数。

题解 1 - python

• 编辑时间：2024-08-11
• 执行用时：169ms
• 内存消耗：23.7MB
• 编程语言：python
• 解法介绍：记忆话dfs遍历所有不想交的可能

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        map2 = defaultdict(list)
        for i, num in enumerate(nums2): map2[num].append(i)
        @cache
        def run(idx: int, last: int) -> int:
            if idx == len(nums1): return 0
            res = run(idx + 1, last)
            for next_idx in map2[nums1[idx]]:
                if next_idx <= last: continue
                res = max(res, run(idx + 1, next_idx) + 1)
            return res
        return run(0, -1)