Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给定两个数字串,相同数字可以连线,问连线不交叉的话最多可以连几条线,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]

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理