Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
将一个二维数组分为加和相等的两拨,问最大的和是多少(不存在的话输出0)
递归DP+memorization,参考了Discussion -> https://leetcode.com/problems/tallest-billboard/solutions/3675264/python3-solution/


 1 #956
 2 #Runtime: 960 ms (Beats 33.33%)
 3 #Memory: 121.3 MB (Beats 11.11%)
 4 
 5 class Solution(object):
 6     def tallestBillboard(self, rods):
 7         """
 8         :type rods: List[int]
 9         :rtype: int
10         """
11         ans = {}
12         def DFS(i, dif):
13             if (i, dif) in ans:
14                 return ans[(i, dif)]
15             if i >= len(rods):
16                 if dif:
17                     return float('-inf')
18                 return 0
19             l = DFS(i + 1, dif + rods[i])
20             skip = DFS(i + 1, dif)
21             s = DFS(i + 1, abs(rods[i] - dif)) + min(dif, rods[i])
22             ans[(i, dif)] = max(l, s, skip)
23             return ans[(i, dif)]
24 
25 
26         return DFS(0, 0)

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