Posted on 2023-05-13 19:44
Uriel 閱讀(34)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
給定兩個數字串，相同數字可以連線，問連線不交叉的話最多可以連幾條線，DP，有參考Discussion
1 #1035
2 #Runtime: 112 ms (Beats 88.11%)
3 #Memory: 13.3 MB (Beats 97.36%)
4
5 class Solution(object):
6 def maxUncrossedLines(self, nums1, nums2):
7 """
8 :type nums1: List[int]
9 :type nums2: List[int]
10 :rtype: int
11 """
12 m, n = len(nums1), len(nums2)
13 dp = [0] * (n + 1)
14 for i in range(1, m + 1):
15 pre = 0
16 for j in range(1, n + 1):
17 cur = dp[j]
18 if nums1[i - 1] == nums2[j - 1]:
19 dp[j] = pre + 1
20 else:
21 dp[j] = max(dp[j-1], cur)
22 pre = cur
23 return dp[n]