1035. 不相交的线（Rating 1805）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

1035. 不相交的线

Rating 1805

思路

连或者不连、选或者不选等类似的问题，一般都是动态规划的思路。

设dp[i][j]表示nums1[0:i+1]、nums2[0:j+1]两段子序列对应等最大连线数即可。

具体见代码

代码

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        dp = [[0 for _ in range(n)] for _ in range(m)] # 初始化为0
        dp[0][0] = int(nums1[0] == nums2[0]) # 初始化边界
        for i in range(1, m): # 仍处理边界
            dp[i][0] = 1 if nums1[i] == nums2[0] else dp[i - 1][0] # 对于边界，相等就连线，不相等就用之前的，一定能保证是最优的
        for i in range(1, n): # 仍处理边界 
            dp[0][i] = 1 if nums1[0] == nums2[i] else dp[0][i - 1] # 对于边界，相等就连线，不相等就用之前的，一定能保证是最优的
        for i in range(1, m):
            for j in range(1, n):
                if nums1[i] == nums2[j]:
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1) # 连
                dp[i][j] = max(dp[i][j], dp[i - 1][j]) # 不连
                dp[i][j] = max(dp[i][j], dp[i][j - 1]) # 不连
        return dp[-1][-1]