1035. Uncrossed Lines
两个 integer array nums1, nums2
如果 nums1[i] == nums2[j] 就可以在他们中间画一条线
问你最多能画几条不交叉的线
Example 1:
https://assets.leetcode.com/uploads/2019/04/26/142.png
Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2
Example 2:
Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
Output: 3
Example 3:
Input: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
Output: 2
思路:
1.假设画出来的线的值是 nums3 好了
nums3 会是 nums1 的 subsequence 同时也会是 nums2 的 subsequence
题目就等于说要找最长的共同 subsequence
蛤 LCS!
class Solution:
def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
m, n = len(nums1), len(nums2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if nums1[i-1] == nums2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[-1][-1]