Posted on 2023-06-25 22:34
Uriel 阅读(10)
评论(0) 编辑 收藏 引用 所属分类:
DP 、
递归 & 分治 、
闲来无事重切Leet Code
将一个二维数组分为加和相等的两拨，问最大的和是多少（不存在的话输出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)