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]